167. 两数之和II-输入有序（Two Sum II - Input Array Is Sorted）

频次 ★★★ · 难度 🟡 · 高频：全厂

题目

非递减数组中找两个数使其和等于 target，返回两数下标（从 1 开始）。要求 O(1) 额外空间，题目保证恰有一解。

示例：

输入: numbers = [2,7,11,15], target = 9
输出: [1,2]

思路

有序 → 首尾双指针：和小于 target 说明左值太小 l++；大于说明右值太大 r--。每次比较排除一个端点，O(n) 收敛。

正确性（排除法）：若 nums[l]+nums[r] < target，则 nums[l] 与任何更左的 r’ 组合更小，l 可安全排除；反之同理。

代码

public int[] twoSum(int[] numbers, int target) {
    int l = 0, r = numbers.length - 1;
    while (l < r) {
        int sum = numbers[l] + numbers[r];
        if (sum == target) return new int[]{l + 1, r + 1}; // 题目要求 1-based
        if (sum < target) l++;
        else r--;
    }
    return new int[]{-1, -1};   // 按题意不会到达
}

复杂度

• 时间：O(n)
• 空间：O(1) —— 这正是不用哈希表的原因

边界条件

• 恰两个元素：直接判定
• 有重复值（[3,3], target 6）：l/r 分居两端，正常命中
• 负数与溢出：Java int 相加可能溢出时用 long（本题范围不溢出，说一句是加分）

变式

• 改为返回所有不重复组合：命中后双侧跳过重复值再继续（即 15. 三数之和 的内层）
• 二分做法：固定一个数、二分找补数，O(n log n)——劣于双指针但体现”有序就想二分”

易错点

• 返回下标是 1-based，忘 +1 是最多的错
• 双指针只适用于有序输入；无序时要么排序（丢失原下标）要么退回哈希版 1. 两数之和
• while (l < r) 不含等号——同一元素不能用两次

面试追问

• 为什么这题用双指针而 1 题用哈希？ 输入性质决定解法：有序白送单调性，双指针 O(1) 空间；无序哈希 O(n) 空间换一趟过。能把两题对照讲清，说明真的理解而非背题
• 双指针会不会跳过正确答案？ 用排除法证明：每次移动只排除”不可能参与解”的端点，解集始终保留在 [l, r] 内

关联题

• 同套路：11. 盛最多水的容器 —— 同款首尾双指针 + 排除法证明
• 进阶：15. 三数之和 —— 外面套一层枚举，本题是它的内核
• 易混：1. 两数之和 —— 无序 + 要原下标，哈希版
• 知识点：有序性 → 单调性 → 每步 O(1) 排除，与二分查找同一逻辑根基，见二分查找