题目链接：
题目描述：
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
算法：
题目非常简单。要在数组中找到两个整数之和为target，那么只需要把数组双层遍历一遍，找出所有可能的组合即可。由于每种输入只会对应一个答案，因此找到之后就可以直接输出。对应的时间复杂度是
，空间复杂度是
。
但是，
即可。可以考虑先将其进行排序，然后寻找元素。用快排的速度为
，然后用二分查找的速度也为
。
当然对于有序的列表来说，可以用首尾递进进行查找。先取nums[0] 和 nums[n - 1]，如果它们相加大于k，则将取nums[0] 与 nums[n - 2]；如果小于k，则取nums[1] 和 nums[n - 1]再进行比较。这样只需要遍历一遍数组，时间复杂度为前面的算法建立了一个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 {};
}
};
