一起刷leetcode(170):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.

For example,

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

C++代码, 本机运行通过!

include <iostream>

include <vector>

include <algorithm>

using namespace std;

class TwoSum
{
    private:
        std::vector<int> v;
    public:
        void add(int a);
        bool find(int a);
};

void TwoSum::add(int a)
{
    v.push_back(a);
}

bool TwoSum::find(int x)
{
    int a, b;
    for(auto it = v.begin(); it != v.end(); ++it)
    {
        a = *it;
        b = x - a;
        auto iter = std::find(v.begin(), v.end(), b);
        if(iter != v.end() && iter != it)
            return true;
    }
    return false;
}


int main()
{
        TwoSum ts;
        ts.add(1);
        ts.add(3);
        ts.add(1);
        cout << ts.find(2) << endl;
        return 0;
}
已邀请:

sumnous - 数据挖掘女博士

赞同来自: geekeeper July


为了去AC,我也是拼了,花了49刀。。。
思路:使用hashtable存储,添加的值作为key,value是key添加的个数。在Python中可以直接使用dict()字典这个数据结构。add()的时间复杂度是O(1),find()的时间复杂度是O(n)。
Python代码(已AC):
    class TwoSum:

        # initialize your data structure here
        def __init__(self):
            self.table = dict()

        # @return nothing
        def add(self, number):
            if not self.table.has_key(number):
                self.table[number] = 1
            else:
                self.table[number] += 1

        # @param value, an integer
        # @return a Boolean
        def find(self, value):
            for k in self.table.keys():
                if k == (value - k) and self.table[k] > 1:
                    return True
                elif k != (value - k) and self.table.has_key(value - k):
                    return True
            return False


再来一个更简洁的Python版本:
    class TwoSum:
        
        # initialize your data structure here
        def __init__(self):
            self.table = dict()

        # @return nothing
        def add(self, number):
            self.table[number] = self.table.get(number, 0) + 1

        # @param value, an integer
        # @return a Boolean
        def find(self, value):
            for i in self.table.keys():
                j = value - i
                if i == j and self.table.get(i) > 1 or i != j and self.table.get(j, 0)>0:
                    return True
            return False

要回复问题请先登录注册