一、编程题：167. 两数之和 II - 输入有序数组（双指针）
1.题目描述
给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列 ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。
以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。
你所设计的解决方案必须只使用常量级的额外空间。LeetCode题目链接。
2.示例1：
输入：numbers = [2,7,11,15], target = 9
输出：[1,2]
解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
3.示例2：
输入：numbers = [2,3,4], target = 6
输出：[1,3]
解释：2 与 4 之和等于目标数 6 。因此 index1 = 1, index2 = 3 。返回 [1, 3]
4.示例3：
输入：numbers = [-1,0], target = -1
输出：[1,2]
解释：-1 与 0 之和等于目标数 -1 。因此 index1 = 1, index2 = 2 。返回 [1, 2] 。
5.提示：
- 2 <= numbers.length <= 3 * 104
- -1000 <= numbers[i] <= 1000
- numbers 按 非递减顺序 排列
- -1000 <= target <= 1000
- 仅存在一个有效答案
二、解题思路
这算是第一次通过双指针的思想将问题解决，不枉练习这么多次双指针的题，由于题目确保有唯一的答案，因此使用双指针一定可以找到答案。；
1.思路
解决方法1（个人想法）：
- Step1.由题目可知该数组已按非递减顺序排列，创建left指向数组的最小值（即数组最左边），right指向数组的最大值（数组最右边）；
- Step2.采用循环来控制双指针的走动，当numbers[left] +numbers[right]==target时，说明已经找到这两个数退出循环；
- Step3.当sum比target大时，right如果在向右边接着取的话sum只会更大（数组已非递减顺序排序），说明最右边的数需要向左边取（right–）；同理当sum比target小时，说明最左边的数需要向右边取（left++）；
- Step4.循环结束后返回其两个数的下标即可（这里下标记得要+1 ）；
该算法时间复杂度：O(n)，其中 n 是数组的长度。两个指针移动的总次数最多为 n 次。
注：在step3这里也许有点疑惑，sum比target大时，只移动right指针–，为什么不移动left–，因为一开始我们就是数组中的最小值和最大值来进行相加，得到值也能有大于小于等于三种情况，当出现大于的情况我们只能从右指针right进行缩减，使其查询范围缩小，所以就不会有left–，right++的情况了；
解决方法2（二分查找）：
由于一开始本人就是用双指针的思路找到了时间复杂度为O(n)的算法，所以没有考虑二分查找进行解决；
待补充；
三、代码实现
。每个代码块都写了注释，方便理解，代码还可以改进；
代码如下（示例）：
解法一：
class Solution { public int[] twoSum(int[] numbers, int target) { //创建满足条件返回的数组，只要长度为2即可 int[] result = new int[2]; //创建双指针，left指向数组的最左边，right指向数组最右边 int left = 0, right = numbers.length - 1; //当left小于right说明无解循环结束 while(left<right){ int sum = numbers[left]+numbers[right]; if(sum == target) break; //满足条件时则退出 else if(sum > target) right--; // 当sum比target大时，说明最右边的数需要向左边取 else if(sum < target) left++; // 当sum比target小时，说明最左边的数需要向右边取 } result[0] = left+1; result[1] = right+1; return result; } }
注：这里有个坑，按下面那个写法执行用时会变得很高
class Solution { public int[] twoSum(int[] numbers, int target) { ... while(left<right){ if(numbers[left]+numbers[right]== target) break; //满足条件时则退出 else if(numbers[left]+numbers[right]> target) right--; // 当sum比target大时，说明最右边的数需要向左边取 else if(numbers[left]+numbers[right]< target) left++; // 当sum比target小时，说明最左边的数需要向右边取 } ... } }
提交结果：
总结
以上就是今天要讲的内容，做题的时候，就是奔着双指针的思路进行解决的，刚开始在想着能不能把双指针和二分查询进行结合，搞了半天也没用搞出来，只能暂缓了。这题双指针最关键的要理清楚left和right指针要怎么移动，这样移动是否漏掉解，经过自己多次思考，发现left和right可以把查询区间不断进行缩小，其算法的正确性可以用数学归纳法来进行证明。所以就赶紧记录一下这个方法，开阔一下思路。
感谢观看，如果有帮助到你，请给题解点个赞和收藏，让更多的人看到。🌹 🌹 🌹
也欢迎你，关注我。👍 👍 👍
原创不易，还希望各位大佬支持一下，你们的点赞、收藏和留言对我真的很重要！！！💕 💕 💕 最后，本文仍有许多不足之处，欢迎各位认真读完文章的小伙伴们随时私信交流、批评指正！
