先看题目：
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案，并且你不能使用两次相同的元素。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6 输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6 输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
Whisper
虽然LeetCode上标签是简单题，虽然思路有，但好久没碰代码了写起代码来还是磕磕碰碰的……
思路：
第一个想到的就是两层遍历了（能力有限啊），对比着目标值，先在数组里逮个值不放（假定为x），然后挨个看target-x值在不在数组里；如果在就匹配成功，如果不在就继续换个值逮……类似于这样：
for（int i = 0 ;i<nums.size();i++）{
for(int j = 0;j<nums.size();j++){
if(i==j)continue;
if(nums[i]+nums[j]==target)return ;
}
}但这个算法一看就过于暴力了……于是我想着如何改进。
我想着既然是两数之和，那么在一个有序数列中和为target的两个数一定在这个数列的两端，就是一左一右取。于是我想着先对这个数组进行排列，然后取一段最大值不大于target的数列，不就一定程度上实现了“剪枝”了么，之后再从两边往中间取值，感觉可行！（这是一个雷点，后面要考！）于是我的第一版代码出炉了：
struct point {
int num;
int pos;
};
class Solution {
public:
static bool cmp(const point a, const point b) {
return a.num < b.num;
}
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
vector<point> points;
for (int i = 0; i < nums.size(); i++) {
point p;
p.num = nums.at(i);
p.pos = i;
points.push_back(p);
}
sort(points.begin(), points.end(), cmp);
/*for (int i = 0; i < points->size();i++) {
cout << points->at(i).num << '\t';
cout << points->at(i).pos << endl;
}*/
int pos = points.size()-1;
for (int i = 0; i < points.size(); i++) {
if (points.at(i).num >= target) {
pos = i;
break;
}
}
int i = 0;
int j = pos;
//cout << "pos:" << pos << endl;
for (j; j > i; j--) {
int sum = target - points.at(j).num;
//cout << "j:" << j << endl;
for (i;i<j; i++) {
//cout << "i:" << i << endl;
if (points.at(i).num == sum) {
res.push_back(points.at(i).pos);
res.push_back(points.at(j).pos);
return res;
}
}
i = 0;
}
return res;
}
};这里我为了方便排序后记录数列的初始坐标，定义了一个point结构体，用于存储数列的值以及其初始坐标。然后就是初始化，排序，取数列，找坐标。其中核心是相对剪枝的两层for循环：
int i = 0;
int j = pos;
for (j; j > i; j--) {
int sum = target - points.at(j).num;
for (i;i<j; i++) {
if (points.at(i).num == sum) {
res.push_back(points.at(i).pos);
res.push_back(points.at(j).pos);
return res;
}
}
i = 0;
}一切看起来挺好的，结果有一个测试用例卡壳了：
输入：nums = [0,4,3,0], target = 0
预计输出：[0,3]
实际输出：[ ]
我的算法没有输出！检查了一遍发现是我的算法没有考虑到有多个重复值的问题，在寻找pos的值时由于是从小往大的找，于是pos会停留在第一个重复值上，也就是[0,0,3,4]的第一个0上，最后导致算法没有输出。
于是我改了一下pos的找寻方向：
int pos = points.size() - 1;
for (int i = points.size() - 1; i >= 0; i--) {
if (points.at(i).num <= target) {
pos = i == points.size() - 1 ? points.size() - 1 : i + 1;
break;
}
}再次提交，之前的测试用例是过了，但新的问题测试用例出现了，是我之前逻辑上埋下的坑！现在遇到的测试用例是这样的：
输入：nums = [-10,-1,-18,-19], target = -19
预计输出：[1,2]
实际输出：[ ]
因为当时没想到有负数的存在，因此那个pos的取值就是多余的！于是我一不做二不休，直接不要那个pos的取值了………现在完整代码长这样：
struct point {
int num;
int pos;
};
class Solution {
public:
static bool cmp(const point a, const point b) { return a.num < b.num; }
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
vector<point> points;
for (int i = 0; i < nums.size(); i++) {
point p;
p.num = nums.at(i);
p.pos = i;
points.push_back(p);
}
sort(points.begin(), points.end(), cmp);
int pos = points.size() - 1;
int i = 0;
int j = pos;
for (j; j >= i; j--) {
int sum = target - points.at(j).num;
for (i; i <= j; i++) {
if (points.at(i).num == sum) {
res.push_back(points.at(i).pos);
res.push_back(points.at(j).pos);
return res;
}
}
i = 0;
}
return res;
}
};过是过了，但算法复杂度不太理想（毕竟直接放弃剪枝了，跟赤裸裸的两层for差不多……）
最后给出原题链接：LeetCode:两数之和