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

题目描述

给定一个升序整数数组和目标值，要求在 O(n) 时间复杂度内找到两个下标，使得它们对应的数字和为目标值。题目保证每组输入都存在唯一解。

解题思路

使用双指针从两端向中间收缩。因为数组有序，若当前和大于目标值，则右指针左移；若当前和小于目标值，则左指针右移。这个思路比暴力枚举更高效。

边界情况

需要注意数组长度为 1、重复数字、以及目标值刚好等于首尾元素的情况。

示例输入/输出

输入： numbers = [2,7,11,15], target = 9

输出： [1, 2]

代码示例

function twoSum(numbers, target) {
  let left = 0;
  let right = numbers.length - 1;
  while (left < right) {
    const sum = numbers[left] + numbers[right];
    if (sum === target) return [left + 1, right + 1];
    if (sum < target) left += 1;
    else right -= 1;
  }
}

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) return new int[]{left + 1, right + 1};
      if (sum < target) left++;
      else right--;
    }
    return new int[]{};
  }
}

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

def two_sum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]
        if total < target:
            left += 1
        else:
            right -= 1

numbers = [2,7,11,15], target = 9

[1, 2]