最近开始撸 LeetCode，在这里做个简单的记录。撸 LeetCode 也不是因为闲来无事，只是觉得在工作之外需要继续锻炼。初步打算按照Problems 的题号来撸，Easy 优先，其他难度的撸不过可以先跳过，以后再来一遍也未尝不可，保持自信心比较重要。

Two Sum

https://leetcode.com/problems/two-sum/

题目大意是给定一个 int 数组，要求返回数组中两个数的下标值的数组，并且满足这两个数的和等于一个给定的目标值。并且假定每一个测试用例只有一个确定的结果。

Solution 1

这题最容易想到的方法，自然是最暴力的两个 for 循环的遍历，实现如下：

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

把这段代码提交上去，成功 Accepted 了，但是花费了688 ms。

这个时间似乎有点惨不忍睹，只击败了 11.73% 的 C++ 提交代码。

看来暴力方法的表现不能让人满意啊，毕竟是 O(n^2) 的复杂度。

Solution 2

接下来考虑一下能不能通过一次循环就完成这个需求。这显然是可以的。我们只需要在一次遍历的过程中把已经遍历过的数和目标值的差值保存起来，然后在这些差值里面查找当前遍历到的这个数。如果查找到的话就说明当前这个数和之前遍历过的某个数的和就是目标值。

这个算法的实现如下：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map<int, int> map_subs;
        vector<int> vec_reslut;
        map<int, int>::iterator it;
        for (size_t i = 0; i < nums.size(); i++) {
            it = map_subs.find(nums[i]);
            if(it != map_subs.end()) {
                vec_reslut.push_back(it->second);
                vec_reslut.push_back(i);
                break;
            }
            map_subs[target - nums[i]] = i;
        }

        return vec_reslut;
    }

再提交一遍，Accept 并且运行时间已经减少到了 24 ms，效果拔群！

通过一次循环，我们成功把运行时间减少到了原来的 1/28，简直是惊人。

不过通过上图，我们发现这次虽然我们把运行时间从 688 ms 减少到了 24 ms，但是还是只击败了 36.21% 的提交，居然还没有到半数，说明还有优化的空间。

Solution 3

通过观察上一个算法，可以发现这里用的 map 是一个有序关联容器，那么在插入新的元素的时候，会对容器进行重新排序，消耗了额外的时间。其实我们在这里只要一个无序关联容器就行，所以可以尝试使用 C++11 中新增的 unordered_map。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> vec_reslut;
        unordered_map<int, int> map_subs;
        unordered_map<int, int>::iterator it;
        for (size_t i = 0; i < nums.size(); i++) {
            it = map_subs.find(nums[i]);
            if(it != map_subs.end()) {
                vec_reslut.push_back(it->second);
                vec_reslut.push_back(i);
                break;
            }
            map_subs[target - nums[i]] = i;
        }

        return vec_reslut;
    }
};

提交之后，运行时间已经减少到了 16 ms。

这次已经成功赶上了大部分人，成为了大多数中的一员。

总结

通过几次改进，Solution 3 已经成为了一个可以接受的算法，但是明显还有更快的算法，只是目前我暂时还没想到，可以先放松一下，其他的事情以后再考虑吧~