LeetCode220720_40、 两数之和 II - 输入有序数组

给你一个下标从 1 开始的整数数组 numbers ，该数组已按 非递减顺序排列  ，请你从数组中找出满足相加之和等于目标数 target 的两个数。如果设这两个数分别是 numbers[index1] 和 numbers[index2] ，则 1 <= index1 < index2 <= numbers.length 。

以长度为 2 的整数数组 [index1, index2] 的形式返回这两个整数的下标 index1 和 index2。

你可以假设每个输入 只对应唯一的答案 ，而且你 不可以 重复使用相同的元素。

你所设计的解决方案必须只使用常量级的额外空间。

 
示例 1：

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

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/two-sum-ii-input-array-is-sorted
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题解，双指针精髓，因为数组已排序，从两端入手可逐步确定数据的和，每次操作索引时仅变化1，数据变化幅度最小，不会错过求和结果对应的两个元素。

基础想法，在初始状态时，取两端点，

① 若数据求和相对target较小，需将数据增大，将小索引++，即数据和变大

② 若数据求和相对target较大，需将数据减小，将大索引--，即数据和变小

③直至两边界相等或求和与target相等，即可return。

双指针求和细节详见LeetCode的@nettee编写的题解，很好，通俗易懂。
一张图告诉你 O(n) 的双指针解法的本质原理（C++/Java） - 两数之和 II - 输入有序数组 - 力扣（LeetCode）

再次转述下，加强自己的理解，双指针求和，每个指针的范围都是0-numbers.length -1。按二维数组展开，上方网页内有图片，在此直接叙述，两个不同数据求和，所以以对角线为分界，选择上三角或下三角进行观察，是等效的。

①若两边界求和 <  target，说明需要增大，增大的话大边界已是最大，只能增加小边界的索引，小边界索引加最大的还小，说明其他元素与小边界索引元素相加也还是小的，所以此小边界索引对应元素不可能为求和中的数据，可小边界++。

②若两边界求和 > target，说明需要减小，减小的话小边界已是最小，只能减小大边界的索引，大边界索引加最小的还大，说明其他元素与大边界索引元素相加也还是大的，所以此大边界索引对应元素不可能为求和中的数据，可大边界--。

③若两边界求和 = target，按照题目要求将索引+1，返回即可。

class Solution{
    public int[] twoSum(int[] numbers, int target){
        int i = 0, j = numbers.length - 1;
        while( i < j){
            int sum = numbers[i] + numbers[j];
            if(sum < target){
                i++;
            } else if(sum > target){
                j--;
            } else{
                return new int[] {i + 1, j + 1};
            }
            
        }
        return new int[] {-1,-1};
    }
}