剑指 Offer II 006 排序数组中两个数字之和

ゝ一世哀愁。 2024-03-27 11:53 48阅读 0赞

给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 0 开始计数 ，所以答案数组应当满足 0 <= answer\[0\] < answer\[1\] < numbers.length 。

假设数组中存在且只存在一对符合条件的数字，同时一个数字不能使用两次。

示例 1：

输入：numbers = \[1,2,4,6,10\], target = 8  
输出：\[1,3\]  
解释：2 与 6 之和等于目标数 8 。因此 index1 = 1, index2 = 3 。  
示例 2：

输入：numbers = \[2,3,4\], target = 6  
输出：\[0,2\]  
示例 3：

输入：numbers = \[-1,0\], target = -1  
输出：\[0,1\]

提示：

2 <= numbers.length <= 3 \* 104  
\-1000 <= numbers\[i\] <= 1000  
numbers 按 递增顺序 排列  
\-1000 <= target <= 1000  
仅存在一个有效答案

方法一：双指针法

因为这个是一个升序的数组，所以我们自然而然可以用一个有规律的方法一个个循环解决，这样就诞生了我们的暴力双循环法。

但问题是这样太慢了，时间上是O(n^2)，所以我们采用双指针，两头并行，就会快很多。

思路是:头尾各放一个指针，让他们的值相加并与target相比较，结果会如下

*  target = low+high
    
     *  直接返回他们俩的数组
 *  target > low+high
    
     *  那就是太小了，所以移动low那个
 *  target < low+high
    
     *  那就是太大了，所以移动high那个

class Solution {
        public int[] twoSum(int[] numbers, int target) {
            //头和尾
            int low = 0;
            int high = numbers.length-1;
            while(low<high){
                int sum = numbers[low]+ numbers[high];
                if(target == sum ){
                    return new int[]{low,high};
                }else if(target>sum){
                    low++;
                }else{
                    high--;
                }
            }
            return new int[]{-1,-1};
        }
    }

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