FilesExpand file tree

 master

/

170_TwoSum.java

Copy path

Blame

More file actions

Blame

More file actions

Latest commit

 

History

History

History

80 lines (66 loc) · 2.11 KB

 master

/

170_TwoSum.java

Copy path

Top

File metadata and controls

• Code
• Blame

80 lines (66 loc) · 2.11 KB

Raw

Copy raw file

Download raw file

Open symbols panel

Edit and raw actions

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

50

51

52

53

54

55

56

57

58

59

60

61

62

63

64

65

66

67

68

69

70

71

72

73

74

75

76

77

78

79

80

//First Tradeoff:

//Add is O(1) but find is O(n)

//Here the thought is using ArrayList to save unique number to instead of using set.iterator().

public class TwoSum {

List<Integer> list;

HashMap<Integer, Integer> map;

public TwoSum(){

list = new ArrayList<Integer>();

map = new HashMap<Integer, Integer>();

}

// Add the number to an internal data structure.

public void add(int number) {

list.add(number);

if(map.containsKey(number)){

map.put(number, map.get(number)+1);

} else{

map.put(number, 1);

}

}

// Find if there exists any pair of numbers which sum is equal to the value.

public boolean find(int value) {

for(int i = 0; i < list.size(); i++){

int first = list.get(i);

int second = value-first;

//Be careful fo this equal scenario.

if(first == second && map.get(first) > 1) return true;

if(first!=second && map.containsKey(second)) return true;

}

return false;

}

}

// Your TwoSum object will be instantiated and called as such:

// TwoSum twoSum = new TwoSum();

// twoSum.add(number);

// twoSum.find(value);

//Another Tradeoff:

//This will cause TLE but the thought is directly

//making add as O(n) but find is O(1)

public class TwoSum {

HashSet<Integer> num;

HashSet<Integer> sum;

public TwoSum(){

num = new HashSet<Integer>();

sum = new HashSet<Integer>();

}

// Add the number to an internal data structure.

public void add(int number) {

if(num.contains(number)) {

sum.add(number*2);

} else{

Iterator<Integer> iterator = num.iterator();

while(iterator.hasNext()){

sum.add(iterator.next()+number);

}

num.add(number);

}

}

// Find if there exists any pair of numbers which sum is equal to the value.

public boolean find(int value) {

return sum.contains(value);

}

}

// Your TwoSum object will be instantiated and called as such:

// TwoSum twoSum = new TwoSum();

// twoSum.add(number);

// twoSum.find(value);