1. Two Sum

题目地址：https://leetcode.com/problems/two-sum/
思路1：双重循环遍历

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

分析：思路很直接，容易想到，容易编写，缺点是算法时间复杂度高 O(n^2)。
思路2：使用哈希表，以空间换时间

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

分析：将每次遇到的值及其位置放到map中，以后每次遇到补充值diff在map中，就表示遇到了解。因为用了索引，所以找补充值不需要从头到尾再遍历，直接可以在map中查找是否存在。该算法的时空复杂度都是O(n)。

不同的算法执行效率差别可达一个数量级，因此创造和使用好算法十分必要。