[HOT 100] 0167. 两数之和 ||

1. 题目链接

167. 两数之和 II - 输入有序数组 - 力扣（LeetCode）

2. 题目描述

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

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

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

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

3. 题目示例

示例 1 :

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

示例 2 :

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

示例 3 :

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

4. 解题思路

1. 初始化指针

int left = 0, right = numbers.length - 1;

left 和 right 是两个指针，分别指向数组的最左端和最右端。

• left 初始化为 0，指向数组的第一个元素。
• right 初始化为 numbers.length - 1，指向数组的最后一个元素。

2. 双指针遍历

while (left < right) {
    int sum = numbers[left] + numbers[right];
    if (sum == target)
        break;
    if (sum > target)
        right--;
    else 
        left++;
}

• 循环条件：while (left < right)，当 left 小于 right 时继续循环，直到两个指针相遇。
• 在循环中，首先计算 sum = numbers[left] + numbers[right]，即当前 left 和 right 所指向的两个数字之和。

根据这个和与目标值 target 的关系，进行不同的操作：

• 如果 sum == target：说明找到了满足条件的两个数。此时直接跳出循环 (break)。
• 如果 sum > target：说明当前的和大于 target，为了减少和的大小，我们将 right 向左移动（right--），即减小右边的数字。
• 如果 sum < target：说明当前的和小于 target，为了增大和的大小，我们将 left 向右移动（left++），即增大左边的数字。
  
  

3. 返回结果

return new int[]{left + 1, right + 1};

• 当找到和为 target 的两个数时，left 和 right 指向这两个数的索引。
• 注意题目要求返回的是从1开始的索引，所以需要将 left 和 right 都加 1。
• 返回的是一个包含这两个索引的数组。

5. 题解代码

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

6. 复杂度分析

• 时间复杂度: 由于我们仅使用了两个指针，且每个指针最多只会移动一次，因此时间复杂度为 O(n)，其中 n 是数组的长度。
• 空间复杂度: 只用了常数级别的额外空间（仅用了几个指针），因此空间复杂度为 O(1)。