1. Two Sum

题目描述：给定一个整数数组，返回其中两个数的下标，使它们的和等于指定的目标值。如：

Given nums = [2, 7, 11, 15], target = 9,
Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

分析：两重循环直接查找一定超时。用哈希表存储每个数的下标，从前往后遍历查找每个数的差值是否存在，复杂度O(n)。还可以先排序，然后左右夹逼，总复杂度O(nlgn)，但排序后下标顺序就打乱了，故不可行，若只返回两个数字则可行。

哈希方法一：需遍历数组两次，第一次将值和对应下标存入哈希表，第二次查找。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;       //数值，对应下标
        vector<int> v;
        
        for (int i = 0; i < nums.size(); i ++)
            map[nums[i]] = i;
        for (int i = 0; i < nums.size(); i ++)
        {
            int gap = target - nums[i];
            if (map.find(gap) != map.end() && map[gap] != i)         //找到差值且不是nums[i]本身
            {
                v.push_back(i);
                v.push_back(map[gap]);
                break;
            }
        }
        return v;
    }
};

哈希方法二：只遍历数组一次，存哈希表的同时查找，第一次没找到，到其差值时就可返回。

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> map;
        vector<int> v;
        
        for (int i = 0; i < nums.size(); i ++)
        {
            int gap = target - nums[i];
            if ( map.count(gap) )     //找到其差值
            {
                v.push_back(i);
                v.push_back(map[gap]);
                break;
            }
            if(map.count(nums[i]) != 1)        //字面是没有记录过或者出现超过一次，此处是没有出现过
            {
                map[nums[i]] = i;
            }
        }
        return v;
    }
};

若返回和为定值的两数字时的排序法：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int i = 0, j = nums.size() - 1;
        vector<int> v;
        while (i < j)
        {
            if (nums[i] + nums[j] == target)
            {
                v.push_back(nums[i]);
                v.push_back(nums[j]);
                break;
            }
            else if (nums[i] + nums[j] < target)
            {
                i ++;
            }
            else
                j --;
        }
        return v;
    }
};