LC167. 两数之和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] 。 示例 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] 。 提示： 2 <= numbers.length <= 3 * 10^4 -1000 <= numbers[i] <= 1000 numbers 按 非递减顺序 排列 -1000 <= target <= 1000 仅存在一个有效答案

题目解析

好的，没问题！我是你的算法老师 AlgoMooc。今天我们来一起攻克 LeetCode 第 167 题。别担心，我会用最通俗易懂的方式，带你一步步搞懂它。

---

### 题目在说什么

这道题其实是在玩一个“找朋友”的游戏。

想象一下，你有一排按身高从矮到高排好队的小朋友（这就是题目里说的“非递减顺序排列”的数组）。每个小朋友身上都贴着一个数字（这就是数组里的元素）。

现在，老师（也就是题目）给了你一个目标数字 target，比如 9。你需要从这排小朋友里，找出两个小朋友，他们身上的数字加起来，正好等于 9。

找到之后，你要报告他们俩在队伍里的位置（注意！题目说下标从 1 开始，也就是第一个小朋友是 1 号，第二个是 2 号，以此类推）。

题目还特别强调了几个规则： 1. 答案唯一：放心，肯定只有一对小朋友能满足条件，不会让你纠结。 2. 不能重复用：你不能让同一个小朋友和自己相加，必须找两个不同的人。 3. 只用常量级额外空间：这个要求有点“抠门”，意思是你不能复制一份新的队伍，只能在原来的队伍上想办法，最多用一两个“小本本”记点东西。

所以，总结一下：在一个从小到大排好序的数组里，找到两个数，使它们的和等于目标值，并返回它们的位置（下标从 1 开始）。

---

### 思路是怎么来的

我们最容易想到的办法是什么？——暴力枚举。

就像你从队伍的第一个小朋友开始，问他：“嘿，你是不是我要找的人？”然后让他和后面每一个小朋友都配对试一下。比如，先让 1 号小朋友和 2 号、3 号、4 号... 所有小朋友都加一遍，看是不是等于 9。如果不是，再让 2 号小朋友和 3 号、4 号... 所有小朋友加一遍。这样肯定能找到答案，但太慢了！如果队伍有 1000 个人，要试将近 50 万次，效率很低。

那有没有更聪明的方法呢？

关键点在于：队伍是按身高（数字大小）排好序的！ 这个信息非常宝贵，我们要好好利用它。

我们可以换个思路，不从头开始一个个试。我们可以派两个“侦察兵”：

• 一个叫 left，站在队伍最前面（最小的数）。
• 一个叫 right，站在队伍最后面（最大的数）。

然后，让这两个侦察兵报告他们身上的数字之和。我们来分析一下这个和与目标值 target 的关系：

1. 如果 `numbers[left] + numbers[right]` 正好等于 `target`：太棒了！就是他们俩！直接报告他们的位置。 2. 如果 `numbers[left] + numbers[right]` 大于 `target`：这说明什么？说明两个数加起来太大了。因为 right 是最大的数，所以我们想，是不是可以让 right 往左走一步，换一个小一点的数来试试？这样和就会变小一点，更有可能接近 target。 3. 如果 `numbers[left] + numbers[right]` 小于 `target`：这说明两个数加起来太小了。因为 left 是最小的数，所以我们想，是不是可以让 left 往右走一步，换一个大一点的数来试试？这样和就会变大一点，更有可能接近 target。

这个思路就像是在玩一个“猜数字”的游戏，只不过我们有两个指针，一个从最小开始，一个从最大开始，根据“和”与目标值的比较结果，不断调整两个指针的位置，直到找到答案。

这个方法就叫 “双指针”。因为队伍是有序的，所以我们可以用两个指针从两端向中间“夹逼”，非常高效。

---

### 代码逐步拆解

我们来看看用 Python 怎么写这个代码：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # 第一步：初始化两个指针
        # left 指向数组的第一个元素（下标 0）
        # right 指向数组的最后一个元素（下标 len(numbers)-1）
        left = 0
        right = len(numbers) - 1

        # 第二步：开始循环，只要 left 还在 right 的左边，就继续找
        # 因为如果 left 和 right 相遇了，说明没找到，但题目保证有答案，所以不会发生
        while left < right:
            # 计算当前两个指针指向的数的和
            current_sum = numbers[left] + numbers[right]

            # 第三步：根据和与 target 的关系，移动指针
            if current_sum == target:
                # 找到答案了！
                # 注意：题目要求下标从 1 开始，所以返回 [left+1, right+1]
                return [left + 1, right + 1]
            elif current_sum < target:
                # 和太小了，需要让 left 往右移动，找一个更大的数
                left += 1
            else: # current_sum > target
                # 和太大了，需要让 right 往左移动，找一个更小的数
                right -= 1

        # 理论上不会执行到这里，因为题目保证有答案
        return []

逐步拆解：

1. 初始化指针：