LeetCode 剑指 Offer 57. 和为s的两个数字

2021-10-11 HGNULB 约 8 分钟

文章信息 9 个分类 3 个标签

分类

LeetCode CodeTop 简单未解决 2-5 美团百度剑指 Offer 剑指 Offer（第 2 版）

题目描述

✅ 剑指 Offer 57. 和为s的两个数字

题意分析

输入是一个递增排序的整数数组和一个目标值 target，要在其中找出两个数使它们的和恰好等于 target，返回这两个数本身而不是下标，任意一组答案都算对。

「递增排序」是这道题最重要的信号：数组已经有序，意味着不必再花代价建立值到位置的映射，也不必自己排序，元素之间的大小关系可以直接拿来做判断和裁剪。题目还保证答案一定存在，所以不需要纠结无解时的返回约定，但工程上仍然应该给出一个兜底返回。

边界方面要注意：数组长度至少为 2；元素可能为负数，也可能有重复值，因此两数之和并不随下标单调变化，只有在固定一个端点之后才呈现单调性；返回的是两个数值，所以重复元素不会造成歧义。

解法：双指针收缩边界

核心思路

最直接的做法是二重循环枚举所有下标对 $(i, j)$ 判断和是否为 target，时间是 $O(n^2)$。瓶颈很明显：它把数组当成一堆无序的数，完全浪费了「已排序」这个前提，每一次失败的枚举都没有为后续枚举提供任何信息。

关键观察在于：把一个指针放在最左端、另一个放在最右端，得到的和处于一个特殊位置——它是当前候选区间里能取到的和的中间态。如果 nums[left] + nums[right] < target，由于 nums[left] 已经是区间里最小的数，它和区间内任何数配对得到的和都不会超过当前这个和，因此 nums[left] 无论如何都凑不出 target，可以永久丢弃；对称地，如果和大于 target，nums[right] 是区间里最大的数，它和区间内任何数配对都太大，同样可以永久丢弃。

于是得到不变量：若答案存在，它一定完整地落在闭区间 [left, right] 内。初始时 left = 0、right = n - 1，整个数组都在区间内，不变量成立；每次移动指针丢弃的都是被证明不可能属于答案的元素，所以不变量在整个循环中始终保持。区间每轮至少缩小 1，因此循环必然终止，而在终止之前必定会撞上答案。

解题步骤

第一步，令 left = 0、right = nums.length - 1，让候选区间覆盖整个数组。之所以从两端出发而不是从中间，是因为只有两端的元素才具备「区间最小」和「区间最大」这种极值身份，也只有极值身份才能支撑「一次排除一整个元素」的推理。

第二步，当 left < right 时计算 sum = nums[left] + nums[right]。循环条件写成严格小于而不是小于等于，是因为题目要求的是两个不同位置上的数，left == right 表示同一个元素自己和自己相加，不是合法答案。

第三步，若 sum == target，直接返回 {nums[left], nums[right]}。题目允许返回任意一组答案，第一次撞上的就是最终答案，不需要继续搜索。

第四步，若 sum < target，执行 left++。理由是 nums[left] 作为区间最小值，与区间内最大的 nums[right] 相加都还不够，它和其余任何数配对只会更小，因此它不可能出现在答案里，必须整体排除。

第五步，否则说明 sum > target，执行 right--。理由完全对称：nums[right] 作为区间最大值，与区间最小的 nums[left] 相加都已经超了，它和其余任何数配对只会更大，同样不可能出现在答案里。

第六步，循环退出说明区间已经收缩到空，返回一个长度为 0 的数组作为兜底。题目保证有解时这一行不会被执行，但保留它可以让方法在所有路径上都有返回值。

以 nums = [2, 7, 11, 15]、target = 9 走一遍：初始 left = 0、right = 3，sum = 2 + 15 = 17，大于 9，说明 15 太大，right 变成 2；此时 sum = 2 + 11 = 13，仍然大于 9，11 同样被排除，right 变成 1；此时 sum = 2 + 7 = 9，正好命中，返回 [2, 7]。再看一个需要左指针移动的例子 nums = [1, 2, 4, 7]、target = 11：left = 0、right = 3 时 sum = 1 + 7 = 8，小于 11，1 太小被排除，left 变成 1；sum = 2 + 7 = 9，仍然偏小，2 也被排除，left 变成 2；sum = 4 + 7 = 11，返回 [4, 7]。整个过程中两个指针加起来只走了数组长度这么多步。

代码实现

class Solution {
    // 若和小于目标，左指针右移。
    public int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;

        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum == target) {
                return new int[]{nums[left], nums[right]};
            }
            if (sum < target) {
                left++;
            } else {
                right--;
            }
        }

        return new int[0];
    }
}

func twoSum(nums []int, target int) []int {
    // 若和小于目标，左指针右移。
    left, right := 0, len(nums)-1

    for left < right {
        sum := nums[left] + nums[right]
        if sum == target {
            return []int{nums[left], nums[right]}
        }
        if sum < target {
            left++
        } else {
            right--
        }
    }

    return []int{}
}

复杂度分析

时间复杂度：$O(n)$。left 只增不减、right 只减不增，两者合起来最多移动 n 次，每次移动只做一次加法和一次比较，因此总步数与数组长度成线性关系。

空间复杂度：$O(1)$。只用了 left、right、sum 三个整型变量，返回的数组是结果本身，不计入额外开销。

关键点总结

有序是双指针的入场券：只要输入有序，就要立刻想到能否用「两端极值」把一次比较转化成一次整体排除，这是把 $O(n^2)$ 降到 $O(n)$ 的通用手法。

用不变量而不是直觉来论证正确性：明确写出「答案一定在 [left, right] 内」，再逐条验证每次移动都不会破坏它，这样的论证比「画个图看着对」更站得住脚。

移动哪一侧由比较结果唯一决定：和偏小就抬高下界，和偏大就压低上界，两个方向不能凭感觉互换，也不能一次同时移动两侧。

分清题目要的是数值还是下标：本题返回数值，指针可以自由移动；若要求返回原始下标且数组无序，就必须改用哈希表，因为排序会破坏下标。

面试视角：先说暴力 $O(n^2)$，再指出它没有利用有序性，接着给出双指针并当场证明排除的合法性，最后主动补一句「如果数组无序怎么办」——哈希表 $O(n)$ 或排序后双指针 $O(n \log n)$，这条完整链路比直接背出答案得分高得多。

易错点总结

循环条件写成 left <= right：nums = [1, 3, 5]、target = 6 会在 left == right == 1 处返回 [3, 3]，把同一个元素用了两次。

命中相等时只记录答案不 return：nums = [1, 2, 3, 4]、target = 5 会在拿到 [1, 4] 之后继续走到 [2, 3]，最终返回的可能不是先命中的那一组。

把 right 初始化成 nums.length：nums = [2, 7, 11, 15] 第一次就访问 nums[4]，直接数组越界。

和小于 target 时误移动 right：nums = [1, 2, 4, 7]、target = 11 会从 sum = 8 一路把 right 减到与 left 相遇，跳过真正的答案 [4, 7]，返回空数组。

和大于 target 时误移动 left：nums = [2, 7, 11, 15]、target = 9 第一步 sum = 17 就把 left 推到 1，[2, 7] 中的 2 被永久丢掉，最终无解。

一轮里同时执行 left++ 和 right--：nums = [1, 2, 3, 4, 5]、target = 6 会跳过 [1, 5] 和 [2, 4]，两个指针直接在 3 处相遇后退出。

用 int 保存和且元素接近上界：nums = [2000000000, 2000000000] 相加溢出成负数，比较结果整体反转，需要用 long 或改写成 nums[left] == target - nums[right] 的形式。

误以为可以先排序再套用本模板返回下标：nums = [3, 2, 4]、target = 6 排序后得到的 [1, 2] 是排序后数组的位置，不是原数组下标。

循环结束后返回 null 而不是空数组：调用方在无解场景下拿到 null 会直接抛出空指针异常。

相似题目

题目	难度	考察点
1. 两数之和	简单	数组无序且要返回下标，只能用哈希表
11. 盛最多水的容器	中等	双指针求最值而非定值，移动依据是短板
15. 三数之和	中等	外层固定一个数，内层套双指针并处理去重
16. 最接近的三数之和	中等	目标从「相等」放宽为「最接近」，需维护最优差
18. 四数之和	中等	两层固定加双指针，重点在剪枝与溢出处理
167. 两数之和 II - 输入有序数组	中等	同为有序双指针，但要求返回从 1 开始的下标
259. 较小的三数之和	中等	统计满足条件的组合数，一次命中贡献一批答案
611. 有效三角形的个数	中等	判定条件变成三角形不等式，需倒序固定最大边
1099. 小于 K 的两数之和	简单	求小于阈值的最大和，命中后仍要继续收缩
LCR 006. 两数之和 II - 输入有序数组	简单	同一模板的另一份题面，输出为下标数组
LCR 007. 三数之和	中等	三数之和的去重版本，考察重复元素的跳过
面试题 16.24. 数对和	中等	需要返回全部数对，命中后两侧指针同时收缩