[LeetCode] 170. Two Sum III - Data structure design

Posted on | In

Problem

Design and implement a TwoSum class. It should support the following operations: add and find.

add - Add the number to an internal data structure.

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

Example 1:

1
2
3
add(1); add(3); add(5);
find(4) -> true
find(7) -> false

Example 2:

1
2
3
add(3); add(1); add(2);
find(3) -> true
find(6) -> false

Explanation

  1. In the add method, We can use a HashMap to record the frequency of the added number. The key is the number, the value is the frequency.

  2. In the find method, we loop through the HashMap keyset’s every number num, the target will be value - num. Then we check if the hashmap contains the target, then we need to consider two cases. The first case is if the target is equal to the current number and the frequency of that number is 1, then we continue. The second case is if the target is not equal to the current number, that means we find a pair that sum to value so we return true. At the end when we loop through all the number, then we return false.

Solution

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
class TwoSum {
    Map<Integer, Integer> hm;

    /** Initialize your data structure here. */
    public TwoSum() {
        hm = new HashMap<>();
    }

    /** Add the number to an internal data structure.. */
    public void add(int number) {
        hm.put(number, hm.getOrDefault(number, 0) + 1);
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    public boolean find(int value) {
        for (int num: hm.keySet()) {
            int target = value - num;
            if (hm.containsKey(target)) {
                if (num == target && hm.get(num) == 1) {
                    continue;
                }
                return true;
            }
        }

        return false;
    }
}

/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum obj = new TwoSum();
 * obj.add(number);
 * boolean param_2 = obj.find(value);
 */