1. 两数之和

题目链接：

1. 两数之和

题目描述：

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

算法：

1. 题目非常简单。要在数组中找到两个整数之和为target，那么只需要把数组双层遍历一遍，找出所有可能的组合即可。由于每种输入只会对应一个答案，因此找到之后就可以直接输出。对应的时间复杂度是，空间复杂度是。

2. 但是，的复杂度显然是比较高的。考虑到，对于数组的第k个元素，nums[k]，我们只需要找到对应的即可。可以考虑先将其进行排序，然后寻找元素。用快排的速度为，然后用二分查找的速度也为，因此时间复杂度为。我们还需要用一个hash表来保存元素的下标，因此空间复杂度为。
   当然对于有序的列表来说，可以用首尾递进进行查找。先取nums[0] 和 nums[n - 1]，如果它们相加大于k，则将取nums[0] 与 nums[n - 2]；如果小于k，则取nums[1] 和 nums[n - 1]再进行比较。这样只需要遍历一遍数组，时间复杂度为。加上前面的排序，总的时间复杂度仍然为。

3. 前面的算法建立了一个hash表来储存下标。事实上，我们可以用储存的下标来表示该数有没有出现过，并且在每次存入一个数的时候，判断是否出现过。如果出现，直接输出二者下标即可。这样，时间复杂度为，空间复杂度为

代码：

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

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map <int, int> label;
        for (int i = 0; i < nums.size(); ++i) {
            // Some values can be same. For instance, { [3, 3], 6 }
            // if we assign value without judge, the result will be (1, 1)
            if (label.count(nums[i]) && 2 * nums[i] == target)
                return { label[nums[i]], i };
            else
                label[nums[i]] = i;
        }

        sort(nums.begin(), nums.end());
        int head = 0, tail = nums.size() - 1;
        while (head < tail) {
            if (nums[head] + nums[tail] == target)
                return { label[nums[head]], label[nums[tail]] };
            if (nums[head] + nums[tail] < target)
                head++;
            if (nums[head] + nums[tail] > target)
                tail--;
        }
        return {};
    }
};

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        map <int, int> label;
        for (int i = 0; i < nums.size(); ++i) {
            // The number we found can't be itself. 
            // For example, { [3, 2, 4]，6} 。Of course 3+3 is the result, but it's wrong. 
            if (label.count(target - nums[i]) && label[target - nums[i]] != i)
                return { label[target - nums[i]], i };
            // We should assign value after judge it. 
            // For example, { [3, 3]，6 }, if we assign value before judge, we will get nothing. 
            label[nums[i]] = i;
        }
        return {};
    }
};