two sum_牛客博客

题目描述：

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

题目中的陷阱：

要求返回两个数的下标不是两个数本身；
不可使用一个数两次；比如[2,7,5,5], target=10, 返回[2,2]错误，应该返回[2,3]

解法1:暴力遍历(Brute Force)

思路简单，第一层遍历每个数，在遍历每个数的同时，遍历其他的数是不是他的补(target-self, complement)

class Solution {
    // 最简单的方法，就是从第一个数n1开始遍历，找到（target-n1）的数的下标;
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // 返回数组，记录两个下标
        vector<int> res {0,0};
        for(int i=0; i<numbers.size(); i++){
            for(int j=i+1; j<numbers.size(); j++){
                if( numbers[j] == (target-numbers[i]) ){
                    res[0] = i+1;
                    res[1] = j+1;
                    return res;
                }
            }
        }
        throw invalid_argument("No two sum solution");
    }
};

复杂度:
时间复杂度：O(nˆ2)
空间复杂度: O(1)

解法2:哈希表(Two-pass Hash Table)

为了改善时间复杂度，我们需要一种高效的方便来查询complement是否在数组中；也就是说，一旦complement存在，我们就要知道它的下标，那么什么结构能方便快速的映射数据和他的下标？Hash Table。
在c++中，无序hash table的查询时间都是O(1)，这个是非常强悍的，也正是我们需要的。解题思路也就明朗了，我们需要两个非嵌套的循环，第一次遍历，我们建立查询表，把数组元素和他们的index建立hash table，通过数据可以map到下标：vale => index
第二次遍历，我们检查每个元素的补(complement = target-numbers[i]),是否存在在table中，一定要注意的是，complement不可以是number[i]本身！，在第一种解法中，无需担心这一点，因为解法一的嵌套循环每次从外层嵌套的index+1开始。

class Solution {
    // 最简单的方法，就是从第一个数n1开始遍历，找到（target-n1）的数的下标;
public:
    vector<int> twoSum(vector<int> &numbers, int target) {
        // 返回数组，记录两个下标
        vector<int> res ;
        unordered_map<int, int> mymap;
        // 建立hash table array's value=> array's index
        for(int i=0; i<numbers.size(); i++){
            mymap[numbers[i]] = i;
        }
        // 第二次遍历，查询是否存在当前数的complement在hash table中
        for(int i=0; i<numbers.size(); i++){
            int complement = target - numbers[i];
            if(mymap.count(complement)!=0 && mymap.at(complement)!=i){
                res = {i+1, mymap.at(complement)+1};
                return res;
            }
        }
        throw invalid_argument("No two sum solution");
    }
};

特别注意：

第二种方法中，在c++的map函数的insert只是插入新的元素，不会更新元素的，比如：

    myMap.insert("a", "apple"     );
    myMap.insert("b", "bannana"   );
    myMap.insert("c", "cherry"    );
    myMap.insert("c", "clementine");

最后的表是："a"=>"apple"; "b"=>"bannana"; "c"=>"cherry" 坑爹啊！这里一定要用operator[ ]才有改的操作；所有这里会有错误，在这个例子下[0,3,4,0] target=0:
0=>0, 3=>1, 4=>2，在第一次遍历的时候，complement为0，对应的i=0，table中的i=0,不成立，直到i=3的时候，查到complement为index=0；因此在用insert没有更新表的情况下，答案是[3,0]，而正确的答案是[0,3]；
用[ ]去添加元素的话，就会有更新的效果，也会得到正确的答案；在c++17中有新的操作纠正了insert的操作；

  std::map<std::string, std::string> myMap;
    myMap.insert_or_assign("a", "apple"     );
    myMap.insert_or_assign("b", "bannana"   );
    myMap.insert_or_assign("c", "cherry"    );
    myMap.insert_or_assign("c", "clementine");

输出：
a : apple
b : bannana
c : clementine