|
5 | 5 | importjava.util.List; |
6 | 6 | importjava.util.Map; |
7 | 7 |
|
8 | | - |
9 | 8 | /** |
10 | 9 | * 170. Two Sum III - Data structure design |
11 | | - * <p> |
12 | | - * Design and implement a_1 class. It should support the following operations: add and find. |
13 | | - * <p> |
| 10 | + * |
| 11 | + * Design and implement aTwoSum class. It should support the following operations: add and find. |
| 12 | + * |
14 | 13 | * add - Add the number to an internal data structure. |
15 | 14 | * find - Find if there exists any pair of numbers which sum is equal to the value. |
16 | | - * <p> |
17 | | - *For example, |
| 15 | + * |
| 16 | + *Example 1: |
18 | 17 | * add(1); add(3); add(5); |
19 | 18 | * find(4) -> true |
20 | 19 | * find(7) -> false |
| 20 | + * |
| 21 | + * Example 2: |
| 22 | + * add(3); add(1); add(2); |
| 23 | + * find(3) -> true |
| 24 | + * find(6) -> false |
21 | 25 | */ |
22 | 26 |
|
23 | | -//Your _1 object will be instantiated and called as such: |
24 | | -//_1 twoSum = new _1(); |
25 | | -//twoSum.add(number); |
26 | | -//twoSum.find(value); |
27 | 27 | publicclass_170 { |
| 28 | +publicstaticclassSolution1 { |
28 | 29 | privateMap<Integer,Integer>map =newHashMap(); |
29 | 30 | privateList<Integer>list =newArrayList(); |
30 | 31 |
|
31 | 32 | // Add the number to an internal data structure. |
32 | 33 | publicvoidadd(intnumber) { |
33 | | -list.add(number); |
34 | | -map.put(number,map.getOrDefault(number,0) +1); |
| 34 | +list.add(number); |
| 35 | +map.put(number,map.getOrDefault(number,0) +1); |
35 | 36 | } |
36 | 37 |
|
37 | 38 | // Find if there exists any pair of numbers which sum is equal to the value. |
38 | 39 | publicbooleanfind(intvalue) { |
39 | | -for (inti =0;i <list.size();i++) { |
40 | | -intval1 =list.get(i); |
41 | | -intval2 =value -val1; |
42 | | -if (map.containsKey(val2)) { |
43 | | -if (val1 ==val2) { |
44 | | -if (map.get(val2) >1) { |
45 | | -returntrue; |
46 | | - } |
47 | | - }else { |
48 | | -returntrue; |
49 | | - } |
| 40 | +for (inti =0;i <list.size();i++) { |
| 41 | +intval1 =list.get(i); |
| 42 | +intval2 =value -val1; |
| 43 | +if (map.containsKey(val2)) { |
| 44 | +if (val1 ==val2) { |
| 45 | +if (map.get(val2) >1) { |
| 46 | +returntrue; |
50 | 47 | } |
| 48 | + }else { |
| 49 | +returntrue; |
| 50 | + } |
51 | 51 | } |
52 | | -returnfalse; |
| 52 | + } |
| 53 | +returnfalse; |
53 | 54 | } |
| 55 | + } |
54 | 56 | } |