[LeetCode] 170. Two Sum III - Data structure design 兩數(shù)之和之三 - 數(shù)據(jù)結(jié)構(gòu)設(shè)計

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

這道題讓我們設(shè)計一個 Two Sum 的數(shù)據(jù)結(jié)構(gòu)，跟 LeetCode 的第一道題 Two Sum 沒有什么太大的區(qū)別，作為 LeetCode 的首題，Two Sum 的名氣不小啊，正所謂平生不會 TwoSum，刷盡 LeetCode 也枉然。記得原來在背單詞的時候，總是記得第一個單詞是 abandon，結(jié)果有些人背來背去還在 abandon，有時候想想刷題其實跟背 GRE 紅寶書沒啥太大的區(qū)別，都是一個熟練功夫，并不需要有多高的天賦，只要下足功夫，都能達(dá)到一個很不錯的水平，套用一句雞湯問來激勵下吧，“有些時候我們的努力程度根本達(dá)不到需要拼天賦的地步”，好了，不閑扯了，來看題吧。不過這題也沒啥可講的，會做 Two Sum 的這題就很簡單了，先來看用 HashMap 的解法，把每個數(shù)字和其出現(xiàn)的次數(shù)建立映射，然后遍歷 HashMap，對于每個值，先求出此值和目標(biāo)值之間的差值t，然后需要分兩種情況來看，如果當(dāng)前值不等于差值t，那么只要 HashMap 中有差值t就返回 True，或者是當(dāng)差值t等于當(dāng)前值時，如果此時 HashMap 的映射次數(shù)大于1，則表示 HashMap 中還有另一個和當(dāng)前值相等的數(shù)字，二者相加就是目標(biāo)值，參見代碼如下：

解法一：

class TwoSum {
public:
    void add(int number) {
        ++m[number];
    }
    bool find(int value) {
        for (auto a : m) {
            int t = value - a.first;
            if ((t != a.first && m.count(t)) || (t == a.first && a.second > 1)) {
                return true;
            }
        }
        return false;
    }
private:
    unordered_map<int, int> m;
};

另一種解法不用 HashMap，而是 unordered_multiset 來做，但是原理和上面一樣，參見代碼如下：

解法二：

class TwoSum {
public:
    void add(int number) {
        s.insert(number);
    }
    bool find(int value) {
        for (auto a : s) {
            int cnt = a == value - a ? 1 : 0;
            if (s.count(value - a) > cnt) {
                return true;
            }
        }
        return false;
    }
private:
    unordered_multiset<int> s;
};

Github 同步地址：

https://github.com/grandyang/leetcode/issues/170

類似題目：

Two Sum

Unique Word Abbreviation

Two Sum IV - Input is a BST

參考資料：

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

https://leetcode.com/problems/two-sum-iii-data-structure-design/discuss/52015/Beats-100-Java-Code

https://leetcode.com/problems/two-sum-iii-data-structure-design/discuss/52035/My-solutions-in-Java-C%2B%2B-and-Python.-O(1)-time-for-add-O(n)-time-for-find-O(n)-space

到此這篇關(guān)于C++實現(xiàn)LeetCode(170.兩數(shù)之和之三 - 數(shù)據(jù)結(jié)構(gòu)設(shè)計)的文章就介紹到這了,更多相關(guān)C++實現(xiàn)兩數(shù)之和之三 - 數(shù)據(jù)結(jié)構(gòu)設(shè)計內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論