目录

1、暴力，超时2、双指针+滑动窗口+条件限制 AC3、观看题解（吸取他人经验）1、二分查找2、双指针3、双指针+二分查找

给定一个已按照升序排列 的有序数组，找到两个数使得它们相加之和等于目标数。

函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。

说明:

返回的下标值（index1 和 index2）不是从零开始的。 你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。 示例:

输入: numbers = [2, 7, 11, 15], target = 9 输出: [1,2] 解释: 2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。

1、暴力，超时

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

2、双指针+滑动窗口+条件限制 AC

在做题提交的过程中发现了几处不容易想到的地方： 1、numbers中的元素是递增的，但是这个递增不是numbers[i]<numbers[i],而是numbers[i]<=numbers[i+1] 2、numbers中的元素有正有负，可能连续好几个都是0 3、一开始我想：首先找到小于等于target的元素个数，这样的话两个值只需要在这些元素中找就可以了，但是事实并非如此。 例如：target=0，numbers[]= {-3,3,.....},如果用numbers[i]<=target，显然只能到第一个元素，所以我又添加了一个限制条件： (i>=1 && numbers[i-1]+numbers[i]==0)(因为观察的是两个元素相加的结果，所以这样肯定是对的) 所以根据思考之后的修改为：

for(int i=0;i<n;i++) { if(numbers[i]<=target || numbers[i]==0 ||(i>=1 && numbers[i-1]+numbers[i]==0)) { num_smaller_than_target++; } else { break; } }

之后只需要在0~num_smaller_than_target-1的范围内寻找两个数就可以了！ 然后使用双指针，一开始L指向0，R指向num_smaller_than_target-1，并且保证L<R来循环 在循环过程中，时时注意sum = numbers[L]+numbers[R], 1、如果sum==target,说明我们已经找到值了，直接退出 2、如果sum<target，说明左值一定过小（右边界由于是从大到小缩减的，此时不做改变，因为也不确定右边界是大是小） 3、如果sum>target,说明右值一定过大，选择减少右值（由于左边界是从小到大的，此时不做改变，因为也不确定左边界是大是小）

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int n = numbers.size(); int flag=0; vector<int> res; int num_smaller_than_target=0; //首先找到小于等于target的元素个数 for(int i=0;i<n;i++) { if(numbers[i]<=target || numbers[i]==0 ||(i>=1 && numbers[i-1]+numbers[i]==0)) { num_smaller_than_target++; } else { break; } } int L=0; int R=num_smaller_than_target-1; //两个指针从两边往中间缩 while(L<R) { int sum = numbers[L]+numbers[R]; if(sum==target) { res.emplace_back(L+1); res.emplace_back(R+1); break; } //当和小于目标，说明，左值肯定过小 else if(sum<target) { L++; } //当和大于目标，说明，右值肯定过大 else { R--; } } return res; } };

因为有要求： 所以我们来验证一下重复结果是否输出一致： 显然正确。

3、观看题解（吸取他人经验）

1、二分查找

在数组中找到两个数，使得它们的和等于目标值，可以首先固定第一个数，然后寻找第二个数，第二个数等于目标值减去第一个数的差。利用数组的有序性质，可以通过二分查找的方法寻找第二个数。为了避免重复寻找，在寻找第二个数时，只在第一个数的右侧寻找。

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int n = numbers.size(); int flag=0; for(int i=0;i<n;i++) { int low = i+1; int high = n-1; while(low<=high) { int mid = (high - low) / 2 + low; if (numbers[mid] == target - numbers[i]) { return {i + 1, mid + 1}; } else if (numbers[mid] > target - numbers[i]) { high = mid - 1; } else { low = mid + 1; } } } return {}; } };

总结：有序序列，查找值固定的数，可以考虑二分查找优化

2、双指针

这是官方题解，和我一开始用的思路是一样的，即双指针。

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int low = 0, high = numbers.size() - 1; while (low < high) { int sum = numbers[low] + numbers[high]; if (sum == target) { return {low + 1, high + 1}; } else if (sum < target) { ++low; } else { --high; } } return {-1, -1}; } };

而我做的一开始排除一些元素的方法好像没有对时间有很多优化。。。

3、双指针+二分查找

class Solution { public: vector<int> twoSum(vector<int>& numbers, int target) { int low = 0, high = numbers.size() - 1; while (low <high) { int middle = (low+high)*0.5; //1、目标在middle左侧，重置high if(numbers[low]+numbers[middle]>target) { high =middle-1; } //2、目标在middle右侧,重置low else if(numbers[high]+numbers[middle]<target) { low = middle+1; } //3、重置low else if(numbers[low]+numbers[high]<target) { low++; } //4、重置high else if(numbers[low]+numbers[high]>target) { high--; } //5、sum等于target else { return {low+1,high+1}; } } return {0,0}; } };

不知道为什么同样的思路，用java速度可以达到1ms，而c++却不行。