How to Design a Two-Sum Data Structure?

  • 时间：2020-09-23 15:50:46
  • 分类：网络文摘
  • 阅读：140 次

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

Two-Sum is a very popular question to prepare for your coding interview. The essence to solve the two-sum question is to use a hash table/set.

Two Sum Interview Questions

  • The Two Sum Algorithm using HashMap in C++/Java
  • C++ Algorithms to Find Pair of Sum Given a Collection of Numbers

Using C++ std::unordered_map or map

Using a hash map to store the counter for each number, and do O(1) in inserting a new number to the list, and O(N) in finding a pair. The special case has to be handled for duplicate number pairs such as 5+5=10. 

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
36
37

class TwoSum {
public:
    /** Initialize your data structure here. */
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        data[number] ++;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for (auto it = data.begin(); it != data.end(); it ++) {
            if (data.find(value - it->first) != data.end()) {
                if (it->first * 2 == value) {
                    if (it->second > 1) { // special case
                        return true;
                    }
                } else {
                    return true;
                }
            }
        }
        return false;
    }
private:
    unordered_map<int, int> data;
};
 
/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */
class TwoSum {
public:
    /** Initialize your data structure here. */
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        data[number] ++;
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for (auto it = data.begin(); it != data.end(); it ++) {
            if (data.find(value - it->first) != data.end()) {
                if (it->first * 2 == value) {
                    if (it->second > 1) { // special case
                        return true;
                    }
                } else {
                    return true;
                }
            }
        }
        return false;
    }
private:
    unordered_map<int, int> data;
};

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

The above unordered_map can be replaced by std::map, however, it might be a bit slower as the map object will maintain its keys in ascending order i.e. O(logN) inserting, and internally, the MAP is implemented using a tree e.g. Red-Black tree while the unordered_map is a hash map.

C++ std::unordered_multiset or multiset

The multiset (the keys are sorted) or unordered_multiset in C++ allows you to insert duplicate numbers into the set. Therefore, by using the multiset, we can simplify the two-sum data structure by checking the counter of a number in the multiset. 

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

class TwoSum {
public:
    /** Initialize your data structure here. */
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        data.insert(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for (const auto &n: data) {
            int c = value == n + n ? 1 : 0;
            if (data.count(value - n) > c) {
                return true;
            }
        }
        return false;
    }
private:
    unordered_multiset<int> data;
};
 
/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */
class TwoSum {
public:
    /** Initialize your data structure here. */
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
        data.insert(number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        for (const auto &n: data) {
            int c = value == n + n ? 1 : 0;
            if (data.count(value - n) > c) {
                return true;
            }
        }
        return false;
    }
private:
    unordered_multiset<int> data;
};

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

The unordered_multiset is faster than multiset as the unordered version does not maintain the order of the keys like the multiset. The time complexity for inserting is O(1) and the find() takes O(N).

Vector and Two Pointer Algorithm

We can use a vector/array to store the numbers. For adding operation, we can use the std::upper_bound to find the position for inserting the element. This takes O(logN).

And as the elements are always sorted, we can use the two pointer algorithm that takes O(N) to find out if a sum pair exists in the vector.

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
36
37
38
39

class TwoSum {
public:
    /** Initialize your data structure here. */
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
       auto it = upper_bound(begin(data), end(data), number);
       data.insert(it, number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        int lo = 0, hi = data.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (data[lo] + data[hi] == value) {
                return true;
            }
            if (data[lo] + data[hi] > value) {
                hi --;
            } else {
                lo ++;
            }
        }
        return false;
    }
private:
    vector<int> data;
};
 
/**
 * Your TwoSum object will be instantiated and called as such:
 * TwoSum* obj = new TwoSum();
 * obj->add(number);
 * bool param_2 = obj->find(value);
 */
class TwoSum {
public:
    /** Initialize your data structure here. */
    TwoSum() {
        
    }
    
    /** Add the number to an internal data structure.. */
    void add(int number) {
       auto it = upper_bound(begin(data), end(data), number);
       data.insert(it, number);
    }
    
    /** Find if there exists any pair of numbers which sum is equal to the value. */
    bool find(int value) {
        int lo = 0, hi = data.size() - 1;
        while (lo < hi) {
            int mid = lo + (hi - lo) / 2;
            if (data[lo] + data[hi] == value) {
                return true;
            }
            if (data[lo] + data[hi] > value) {
                hi --;
            } else {
                lo ++;
            }
        }
        return false;
    }
private:
    vector<int> data;
};

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

All the above Two-Sum data structures require O(N) space complexity to store the numbers.

–EOF (The Ultimate Computing & Technology Blog) —

推荐阅读：
有些食物发芽后营养价值会变得更高　 春季健康食谱：可以适当吃些新鲜蚕豆　 多个品牌婴幼儿配方乳粉被曝配方都一样　 新食品安全法“史上最严”建立惩罚制度　 适合在夏天吃的既简单又美味的凉拌菜　 薏米与红豆的多种搭配煮法可健脾养血　 好时巧克力1年3上黑榜 违规使用维生素E　 近些年被曝光的大米安全事件一览　 夏日进补：男不离韭，女不离藕之解读　 “僵尸肉”蹿上餐桌拷问食品安全监管　
评论列表
添加评论