LeetCode 167. 两数之和 II - 输入有序数组

约 6 分钟
文章信息 15 个分类 4 个标签
分类
LeetCode CodeTop 中等 未解决 10-20 字节跳动 美团 快手 腾讯 百度 滴滴 小米 商汤 虾皮 面试经典 150 题
标签
数组 双指针 二分查找 nSum 问题
目录

题目描述

✅ 167. 两数之和 II - 输入有序数组

image-20230309213657371

题意分析

在一个非递减排列的整数数组里找出两个数，使它们相加等于 target，返回这两个数的下标。要点全在细节里：返回的是下标而不是数值，而且是从 1 开始编号的下标，第一个下标要小于第二个。

题面给出的三条约束，每一条都在往解法上指路。第一条是数组已经有序——这是与 1. 两数之和 唯一的结构性差别，也是本题存在的全部理由；有序意味着「当前这一对偏大还是偏小」可以直接翻译成「该动哪根指针」。第二条是题目保证恰好存在一个有效答案，所以不需要考虑多解如何取舍，也不需要考虑无解如何返回，找到即可立刻收工。第三条是要求只使用常量级的额外空间，这一条直接把「开哈希表记录已见过的数」这条最省事的路堵死了——那条路要 $O(n)$ 空间，正是出题人想排除的答案。

还有一条容易被忽略的隐含约束：不能重复使用同一个元素。也就是两个下标必须不同，numbers[i] + numbers[i] 不算数。

边界情形：数组可能含负数和零（如 numbers = [-1, 0]、target = -1）；数组里可能有重复元素（如 numbers = [3, 3]、target = 6，答案是 [1, 2]，两个相等的数分属不同下标是允许的）；数组长度最小为 2，此时唯一的一对就是答案；数值范围在 [-1000, 1000]，两数之和最大不过 2000，普通的 32 位整数完全够用，不存在溢出风险。

解法：有序数组双指针

核心思路

暴力枚举下标对需要 $O(n^2)$，逐个固定左端点再二分也要 $O(n \log n)$。数组已经有序，可以用左右指针一次排除一个不可能出现在答案中的下标。

维护不变量：唯一答案始终位于闭区间 [left, right] 内。令 sum = numbers[left] + numbers[right]：

  • sum < target：left 与当前区间最大值相加仍偏小，因此 left 不可能参与答案，只能右移；
  • sum > target：right 与当前区间最小值相加仍偏大，因此 right 不可能参与答案，只能左移；
  • sum == target：找到唯一答案，返回两个下标加 1。

每次移动都排除了一个已证明无解的端点，所以不会漏解；区间持续缩小，最终必然命中。循环使用 left < right，避免重复使用同一个元素。

解题步骤

  1. 令 left = 0、right = numbers.length - 1。
  2. 当 left < right 时计算两端元素之和 sum。
  3. 若 sum == target，返回 [left + 1, right + 1]。
  4. 若 sum < target，执行 left++；否则执行 right--。
  5. 题目保证恰有一解；循环后的空数组只是满足函数返回要求。

例如 [2, 7, 11, 15]、target = 18：2 + 15 < 18，排除 2；7 + 15 > 18，排除 15；最后 7 + 11 = 18，返回 [2, 3]。

代码实现

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int left = 0;
        int right = numbers.length - 1;
        while (left < right) {
            int sum = numbers[left] + numbers[right];
            if (sum == target) {
                return new int[]{left + 1, right + 1};
            } else if (sum < target) {
                // 数组升序，左指针右移才能增大当前和。
                left++;
            } else {
                right--;
            }
        }
        return new int[0];
    }
}

func twoSum(numbers []int, target int) []int {
    left := 0
    right := len(numbers) - 1
    for left < right {
        sum := numbers[left] + numbers[right]
        if sum == target {
            return []int{left + 1, right + 1}
        } else if sum < target {
            // 当前和偏小，只能移动左指针增大和。
            left++
        } else {
            right--
        }
    }
    return []int{}
}

复杂度分析

  • 时间复杂度：$O(n)$。每轮至少有一个指针向内移动，最多移动 n - 1 次。
  • 空间复杂度：$O(1)$。除返回结果外只使用常数个变量。

关键点总结

  • 双指针成立的依据是数组有序，以及每轮都能安全淘汰一个端点。
  • sum 偏小移动左指针，偏大移动右指针；方向来自单调性，不是模板记忆。
  • left < right 保证两个下标不同，返回时还要转换为 1 基下标。
  • 面试可按「暴力 $O(n^2)$ → 逐个二分 $O(n \log n)$ → 双指针 $O(n)$」说明优化过程。

易错点总结

  • 返回的是 1 基下标，左右下标都要加 1。
  • 循环写成 left <= right 可能把同一元素使用两次，应严格使用 <。
  • sum < target 时误移动右指针，会让和更小；移动方向必须由有序性推导。
  • 数组是非递减而非严格递增，[3, 3] 可以组成目标值 6。
  • 本题要求常量额外空间，哈希表虽然能求解，却没有利用已排序条件。

相似题目

题目 难度 考察点
1. 两数之和 简单 输入无序，只能用哈希表边扫边查，是本题去掉「有序」前提后的对照组
LCR 006. 两数之和 II - 输入有序数组 简单 与本题同题异名，仅返回值改为 0 基下标，可用来检验下标偏移是否写对
剑指 Offer 57. 和为s的两个数字 简单 同样是有序数组求两数之和，但返回数值而非下标，省去了 1 基转换的坑
面试题 16.24. 数对和 中等 输入无序且要求返回所有数对，需先排序，命中后两端同时内移继续找
1099. 小于 K 的两数之和 简单 判据从「等于」放宽成「小于」，命中时不能停，要在满足条件时记录并右移左指针
1679. K 和数对的最大数目 中等 求能配出多少对而非找一对，命中后左右指针同时内移并累加计数
15. 三数之和 中等 外层枚举第一个数，内层套本题的双指针，难点转移到三处去重上
16. 最接近的三数之和 中等 目标从「恰好相等」变成「差值最小」，指针移动规则不变但要额外记录最优差
18. 四数之和 中等 两层枚举加一层双指针，需要提前剪枝并注意四数相加的整型溢出
259. 较小的三数之和 中等 求满足条件的三元组个数，靠 right - left 一次性统计一批而非逐个数
611. 有效三角形的个数 中等 判据换成三角形不等式，改为固定最大边、在其左侧收缩双指针
LCR 007. 三数之和 中等 与 15 题同题异名，可用来复查排序后跳过重复元素的写法
11. 盛最多水的容器 中等 同为对撞双指针，但淘汰依据是「较矮的一侧不可能更优」而非和的大小
653. 两数之和 IV - 输入二叉搜索树 简单 有序性藏在中序遍历里，可用两个方向的中序迭代器模拟本题的左右指针
170. 两数之和 III - 数据结构设计 简单 改成支持动态插入的数据结构，需要在插入与查询的复杂度之间做取舍