来源

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/two-sum-ii-input-array-is-sorted/

描述

给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。
函数应该返回这两个下标值index1和index2，其中index1必须小于index2。

说明:
返回的下标值（index1和index2）不是从零开始的。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。

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

题解

暴力法和哈希表法均可解，但这两种解法都没有用到输入数组已经排序的性质，使用双指针可以做的更好。

使用两个指针，初始分别位于第一个元素和最后一个元素位置，比较这两个元素之和与目标值的大小。如果和等于目标值，我们发现了这个唯一解。如果比目标值小，我们将较小元素指针增加一。如果比目标值大，我们将较大指针减小一。移动指针后重复上述比较知道找到答案。

  1. class Solution {
  2.     public int[] twoSum(int[] numbers, int target) {
  3.         int[] res = new int[] {-1, -1};
  4.         if (numbers.length < 2) return res;
  6.         int lo = 0, hi = numbers.length - 1;
  7.         while (lo < hi) {
  8.             int sum = numbers[lo] + numbers[hi];
  9.             if (sum > target) {
  10.                 hi--;
  11.             } else if (sum < target) {
  12.                 lo++;
  13.             } else {
  14.                 res[0] = lo + 1;
  15.                 res[1] = hi + 1;
  16.                 break;
  17.             }
  18.         }
  20.         return res;
  21.     }
  22. }

复杂度分析

  • 时间复杂度：167. 两数之和 II - 输入有序数组(Two Sum II - Input array is sorted) - 图1。每个元素最多被访问一次，共有n个元素。
  • 空间复杂度：167. 两数之和 II - 输入有序数组(Two Sum II - Input array is sorted) - 图2，只是用了两个指针。