170

170. Two Sum III - Data structure design (Easy)

Design a data structure that accepts a stream of integers and checks if it has a pair of integers that sum up to a particular value.

Implement the TwoSum class:

• TwoSum() Initializes the TwoSum object, with an empty array initially.
• void add(int number) Adds number to the data structure.
• boolean find(int value) Returns true if there exists any pair of numbers whose sum is equal to value, otherwise, it returns false.

 

Example 1:

Input
["TwoSum", "add", "add", "add", "find", "find"]
[[], [1], [3], [5], [4], [7]]
Output
[null, null, null, null, true, false]

Explanation
TwoSum twoSum = new TwoSum();
twoSum.add(1);   // [] --> [1]
twoSum.add(3);   // [1] --> [1,3]
twoSum.add(5);   // [1,3] --> [1,3,5]
twoSum.find(4);  // 1 + 3 = 4, return true
twoSum.find(7);  // No two integers sum up to 7, return false

 

Constraints:

• -105 <= number <= 105
• -231 <= value <= 231 - 1
• At most 104 calls will be made to add and find.

Companies:
LinkedIn

Related Topics:
Array, Hash Table, Two Pointers, Design, Data Stream

Similar Questions:

• Two Sum (Easy)
• Unique Word Abbreviation (Medium)
• Two Sum IV - Input is a BST (Easy)

Solution 1. Map

// OJ: https://leetcode.com/problems/two-sum-iii-data-structure-design/
// Author: github.com/lzl124631x
// 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;
    }
};

Solution 2. Two Pointers

// OJ: https://leetcode.com/problems/two-sum-iii-data-structure-design/
// Author: github.com/lzl124631x
// Time:
//      TwoSum: O(1)
//      add: O(logN)
//      find: O(N)
// Space: O()
class TwoSum {
    multiset<int> s;
public:
    TwoSum() {}
    void add(int n) {
        s.insert(n);
    }
    bool find(int n) {
        if (s.empty()) return false;
        auto i = s.begin(), j = prev(s.end());
        while (i != j) {
            int sum = *i + *j;
            if (sum == n) return true;
            if (sum > n) --j;
            else ++i;
        }
        return false;
    }
};