170.Two Sum III - Data structure design

Tags: Design Hash Table Easy

Links: https://leetcode-cn.com/problems/two-sum-iii-data-structure-design/

---

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:

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

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

---

class TwoSum {
    vector<int> v;
public:
    /** Initialize your data structure here. */
    TwoSum() {}

    /** Add the number to an internal data structure.. */
    void add(int number) {
        v.push_back(number);
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        if (v.empty()) return false;
        sort(v.begin(), v.end());

        int n = v.size();
        int start = 0, end = n - 1;
        while (start < end) {
            int sum = v[start] + v[end];
            if (sum == value) return true;
            else if (sum < value) ++start;
            else --end;
        }
        return false;
    }
};

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

其实这道题目本来不该用vector实现的，但是还是作死试了下，还是可以通过的。

回归经典解法，利用unordered_map求解。

class TwoSum {
    unordered_map<int, int> um;
public:
    /** Initialize your data structure here. */
    TwoSum() {}

    /** Add the number to an internal data structure.. */
    void add(int number) {
        ++um[number];
    }

    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        if (um.empty()) return false;
        for (auto e : um) {
            int target = value - e.first;
            auto pos = um.find(target);
            if (pos != um.end() && 
            (target != e.first || (target == e.first && um[target] >= 2)))
                return true;
        }
        return false;
    }
};

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