Question

Formatted question description: https://leetcode.ca/all/170.html


 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.

 For example,
 add(1); add(3); add(5);
 find(4) -> true
 find(7) -> false

Algorithm

HashMap to hold remainder.

Establish a mapping between each number and the number of occurrences, and then traverse the HashMap. For each value, first find the difference t between this value and the target value, and then you need to look at it in two cases.

  • If the current value is not equal to the difference t, then return True as long as there is a difference t in the HashMap, or when the difference t is equal to the current value,
  • If the number of mapping times of the HashMap is greater than 1, it means that there is another number in the HashMap that is equal to the current value, and the addition of the two is the target value

Code

Java

  • 
        // time: O(N)
        // space: O(N)
        public class TwoSum {
    
            // number to frequency
            private HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
    
            public void add(int number) {
                if (hm.containsKey(number)) {
                    hm.put(number, hm.get(number) + 1);
                } else {
                    hm.put(number, 1);
                }
            }
    
            public boolean find(int value) {
                for (Integer oneNumber : hm.keySet()) {
                    int target = value - oneNumber;
                    if (hm.containsKey(target)) {
                        // @note: for case: add=3, add=3, target=6
                        if (oneNumber == target && hm.get(target) < 2) {
                            continue;
                        }
                        return true;
                    }
                }
                return false;
            }
        }
    
    
  • // OJ: https://leetcode.com/problems/two-sum-iii-data-structure-design/
    // Time:
    //      TwoSum: O(1)
    //      add: O(logN)
    //      find: O(NlogN)
    // Space: O(N)
    class TwoSum {
        map<long, int> m;
    public:
        TwoSum() {}
        void add(int n) {
            m[n]++;
        }
        bool find(int n) {
            for (auto &[a, cnt] : m) {
                long b = n - a;
                if (a > b) return false;
                if (a == b) return cnt > 1;
                if (m.count(b)) return true;
            }
            return false;
        }
    };
    
  • class TwoSum(object):
    
      def __init__(self):
        """
        initialize your data structure here
        """
        self.nums = {}
    
      def add(self, number):
        """
        Add the number to an internal data structure.
        :rtype: nothing
        """
        self.nums[number] = self.nums.get(number, 0) + 1
    
      def find(self, value):
        """
        Find if there exists any pair of numbers which sum is equal to the value.
        :type value: int
        :rtype: bool
        """
        d = self.nums
        for num in d:
          t = value - num
          if t in d:
            if t == num:
              if d[t] >= 2:
                return True
            else:
              return True
    
        return False
    
    # Your TwoSum object will be instantiated and called as such:
    # twoSum = TwoSum()
    # twoSum.add(number)
    # twoSum.find(value)
    
    

All Problems

All Solutions