【leetcode刷题笔记】001.Two Sum

日期：20180910

题目描述：

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.

Examples：

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

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

详解：

这道题的难度是easy，没有多想直接遍历，下面是我的解。（C++）

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> sum;
        int i,j;
        for(int i=0;i<nums.size()-1;i++)
            for(int j=i+1;j<nums.size();j++)
                if(nums[i]+nums[j]==target){
                    sum.push_back(i);
                    sum.push_back(j);
                    return sum;
                }
    }
};

提交完结果168ms，击败了4.35%的C++提交者。我点开了第一名的答案，用时只有4ms。第一天刷leetcode就给我上了一课，原来人与人之间是有差距的。下面是4ms的代码。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) 
    {
        unordered_map<int, int> myMap;            //使用无序映射，内部为哈希表实现
        vector<int> res;
        int size = nums.size();
        for (int i = 0; i < size; i++) {
            int val = target - nums[i];
            if (myMap.find(val) != myMap.end()) { //找到了对应的值
                res.push_back(myMap[val]);
                res.push_back(i);
                return res;
            }
            myMap[nums[i]] = i;
        }
    }
};

非常简洁的代码，速度非常快，简单来说之所以这么快是因为使用了无序映射。也就是代码中的unordered_map。无序映射的内部是由哈希表来实现的，所以在查找的时候速度非常的快，是常数的时间复杂度。而这道题目最核心的工作就是查找，无论哪一种方法都是遍历一遍数组，对于每一个遍历到的数，找到一个和它匹配的数就可以了。而我一开始自己做的方法，对于每一个数，找到和它匹配的数的方法就是再遍历一遍，这样的时间复杂度是O(n^2)。而用哈希表，查找的时间复杂度是常数，总共的时间复杂度是O(n)。

然后举个栗子来说明示例代码的过程：

例如输入是[1,2,3,6,7,10]和5，最终期待的输出是[1,2]。我们来看一下这个代码是怎么实现的。

遍历每一个元素，首先是i=0的时候，val = target - nums[0] = 4，if条件不成立，因为此时map中还什么都没有。这是跳过判断语句，执行myMap[nums[i]] = i;也就是给map中加入一个映射：1->0。意思就是说，值为1的数在下标为0的位置。

此时map中的键值关系情况：
1->0

然后开始遍历到第二个元素，也就是i = 1，nums[1] = 2，val = 3，目前map里只有一个键为1的元素，并没有键为3的元素，所以条件判断依然不会成立。然后执行myMap[nums[i]] = i，加入了一个2->1的键值对。

此时map中的键值关系情况：
1->0

2->1

然后遍历到第三个元素，也就是nums[2] = 3，val = 2，这是if条件判断语句终于能成立了，因为map里面有键为2的值。这时就匹配上了。返回的顺序是先返回res.push_back(myMap[val])，因为要先让下标小的数在前面，不然顺序反了输出结果就变成[2,1]了。

于是就大功告成了！

总结：

在C++中，map底层是用红黑树实现的，是有序的结构搜索，插入，删除都是O(logn)的时间复杂度。

unordered_map底层用哈希表实现，搜索是O(1)的时间复杂度。对于查找问题，可以考虑无序映射，即unordered_map。