跳至主要內容

两数之和 II：双指针合法性的严格数学证明

老张2026/4/30大约 8 分钟

两数之和 II：双指针合法性的严格数学证明

适读人群：Java 后端工程师、算法入门到中阶 | 阅读时长：约 16 分钟 | 难度：⭐⭐

开篇故事

很多人第一次见到双指针的时候，感觉就是"好像对"，但又说不清楚为什么对。我讲过很多次双指针，问学员"为什么移动左指针而不是右指针？"，十个人里有八个说不清楚。

双指针的直觉很好建立，但"为什么不会漏掉答案"这个问题，真的能说清楚的人很少。

今天用 LeetCode 167 来把这个问题彻底讲透。这道题是双指针最经典的入门题，代码只有几行，但背后的数学证明值得深入推敲。搞清楚了这道题的正确性证明，后面的盛水容器（11）、三数之和（15）、颜色分类（75）都能用同样的框架理解。

一、题目解析

题目（LeetCode 167）： 给一个下标从 1 开始的整数数组 numbers，该数组已按非递减顺序排列。找到两个数，使得它们相加之和等于目标数 target。设这两个数为 numbers[index1] 和 numbers[index2]，要求 1 <= index1 < index2 <= numbers.length。以 [index1, index2] 形式返回（下标从1开始）。

示例：

  • numbers = [2,7,11,15]，target = 9，输出：[1, 2]（2+7=9）
  • numbers = [2,3,4]，target = 6，输出：[1, 3]（2+4=6）

题目保证恰好有一个解。

二、解法一：哈希表（O(n)时间，O(n)空间）

public class Solution1 {
    public int[] twoSum(int[] numbers, int target) {
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < numbers.length; i++) {
            int complement = target - numbers[i];
            if (map.containsKey(complement)) {
                return new int[]{map.get(complement) + 1, i + 1};
            }
            map.put(numbers[i], i);
        }
        return new int[]{-1, -1};
    }
}

复杂度分析

  • 时间复杂度：O(n)。
  • 空间复杂度：O(n)。哈希表空间。

注意：这种方法没有利用数组有序的特性，对于这道题来说"大材小用"了。

三、解法二：二分查找（O(n log n)）

public class Solution2 {
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length - 1; i++) {
            int complement = target - numbers[i];
            // 在 [i+1, n-1] 内二分查找 complement
            int lo = i + 1, hi = numbers.length - 1;
            while (lo <= hi) {
                int mid = lo + (hi - lo) / 2;
                if (numbers[mid] == complement) {
                    return new int[]{i + 1, mid + 1};
                } else if (numbers[mid] < complement) {
                    lo = mid + 1;
                } else {
                    hi = mid - 1;
                }
            }
        }
        return new int[]{-1, -1};
    }
}

复杂度分析

  • 时间复杂度：O(n log n)。外层 O(n)，内层二分 O(log n)。
  • 空间复杂度：O(1)。

四、解法三最优：双指针（O(n)时间，O(1)空间）

思路与合法性证明

双指针：左指针 lo 从头开始，右指针 hi 从尾开始。

  • 若 numbers[lo] + numbers[hi] == target：找到答案，返回。
  • 若 numbers[lo] + numbers[hi] < target：和太小，需要增大，移动 lo++（因为数组有序，lo 右移会增大和）。
  • 若 numbers[lo] + numbers[hi] > target：和太大，需要减小，移动 hi--（因为数组有序，hi 左移会减小和）。

核心问题：为什么不会漏掉答案？

设答案是 (a, b)，其中 a < b（在数组中）。我们要证明：双指针算法一定会在某步到达 (lo=a_idx, hi=b_idx) 的状态。

证明（反证法）：

假设双指针漏掉了答案 (a, b)。漏掉意味着两件事情中的一件：

  1. 当 lo == a_idx 时，hi 已经移过了 b_idx（hi < b_idx），所以错过了 b。
  2. 当 hi == b_idx 时，lo 已经移过了 a_idx（lo > a_idx），所以错过了 a。

分析情况 1：当 lo == a_idx 时，算法必然对某个 hi' > b_idx 进行了 hi-- 操作（移到了 b_idx 左边）。

hi-- 操作的触发条件是 numbers[lo] + numbers[hi'] > target。

而此时 lo = a_idx，所以 numbers[a_idx] + numbers[hi'] > target = numbers[a_idx] + numbers[b_idx]，即 numbers[hi'] > numbers[b_idx]。

但 hi' > b_idx 且数组升序，所以 numbers[hi'] >= numbers[b_idx]。如果 numbers[hi'] > numbers[b_idx]，则 hi' > b_idx 是合理的，算法确实会对 hi' 执行 hi--，一直减到 hi = b_idx，然后找到答案。如果 numbers[hi'] == numbers[b_idx]，那其实 hi' 也是一个等效答案位置，不会漏掉。

综上，情况 1 不可能导致漏掉答案。情况 2 同理。

更直观的理解（消去论证）：

考虑所有 (i, j) 对，i < j。总共有 O(n²) 对。双指针每一步都能安全地排除至少一行或一列的候选对：

  • lo++：排除 (lo, j) for all j > hi（因为这些对的和 >= numbers[lo] + numbers[hi+1] > target，等等，这里需要更精确的论证...）

准确的消去论证：

当 numbers[lo] + numbers[hi] < target 时，执行 lo++：

排除了所有以 lo 为左端的对 (lo, j), j <= hi。为什么可以排除？因为 j <= hi 时 numbers[j] <= numbers[hi]，所以 numbers[lo] + numbers[j] <= numbers[lo] + numbers[hi] < target，这些对的和都小于 target，不是答案。

当 numbers[lo] + numbers[hi] > target 时，执行 hi--：

排除了所有以 hi 为右端的对 (i, hi), i >= lo。为什么可以排除？因为 i >= lo 时 numbers[i] >= numbers[lo]，所以 numbers[i] + numbers[hi] >= numbers[lo] + numbers[hi] > target，这些对的和都大于 target，不是答案。

每步至少排除一个候选对，且不会错误排除答案对，所以算法最终一定能找到（或排除完所有非答案后宣告无解）。

Mermaid 图：双指针移动逻辑

完整代码

public class Solution3 {
    public int[] twoSum(int[] numbers, int target) {
        int lo = 0, hi = numbers.length - 1;

        while (lo < hi) {
            int sum = numbers[lo] + numbers[hi];

            if (sum == target) {
                return new int[]{lo + 1, hi + 1};  // 题目下标从1开始
            } else if (sum < target) {
                lo++;   // 和太小，增大左端
            } else {
                hi--;   // 和太大，减小右端
            }
        }

        // 题目保证有解，不会到达这里
        return new int[]{-1, -1};
    }

    public static void main(String[] args) {
        Solution3 sol = new Solution3();
        System.out.println(Arrays.toString(
                sol.twoSum(new int[]{2,7,11,15}, 9)));  // [1, 2]
        System.out.println(Arrays.toString(
                sol.twoSum(new int[]{2,3,4}, 6)));      // [1, 3]
        System.out.println(Arrays.toString(
                sol.twoSum(new int[]{-1,0}, -1)));      // [1, 2]
    }
}

复杂度分析

  • 时间复杂度：O(n)。lo + hi 每步至少减少一（lo++ 或 hi--），最多执行 n-1 步。
  • 空间复杂度：O(1)。

五、举一反三：同类题与模板

题号题目双指针的应用
1两数之和（无序）不能用双指针，用哈希表
15三数之和排序 + 外层固定一个 + 内层双指针
16最接近的三数之和同上，记录最近距离
18四数之和两层固定 + 内层双指针
11盛最多水的容器双指针贪心，每步移动较短的那侧

双指针模板（有序数组，找满足条件的对）：

int lo = 0, hi = n - 1;
while (lo < hi) {
    int cur = f(arr[lo], arr[hi]);  // 当前状态的某个量
    if (cur == target) {
        // 找到答案
        lo++; hi--;  // 或者根据题意只移动一端
    } else if (cur < target) {
        lo++;   // 增大
    } else {
        hi--;   // 减小
    }
}

六、踩坑实录

坑一：返回下标忘记加 1

题目要求返回下标从 1 开始，但代码里用的是从 0 开始的数组下标。最后返回时要 lo + 1 和 hi + 1，忘记加 1 就全错了。这种小细节不要掉以轻心。

坑二：循环条件写成 lo <= hi 导致死循环或错误

当 lo == hi 时，两个指针指向同一个元素，numbers[lo] + numbers[hi] = 2 * numbers[lo]。如果 target 恰好等于两倍的某个元素，会误认为找到了答案，但实际上要求 index1 < index2，同一个位置不算。用 lo < hi 确保两指针始终不同。

坑三：在无序数组上用双指针

双指针的正确性完全依赖于数组有序。LeetCode 1（无序的两数之和）如果强行用双指针会出错。遇到两数之和类问题，先判断是否有序，有序才能用双指针，无序只能用哈希表。

坑四：整数溢出

numbers[lo] + numbers[hi] 中，numbers[i] 的范围是 [-1000, 1000]，target 也在类似范围内，int 不会溢出。但如果题目换成更大的数，比如 numbers[i] 可以是 Integer.MAX_VALUE / 2，相加就溢出了。保险起见可以用 long 转换：(long)numbers[lo] + numbers[hi]。

坑五：认为双指针可以直接扩展到三数之和

三数之和不能直接用一组双指针解决。正确做法是：排序后，外层 for 循环固定第一个数，内层再用双指针找另外两个数。这个扩展不是"双指针直接用三个指针"，而是"降一维后再用双指针"。

七、总结

双指针不是一个技巧，而是一种基于"消去论证"的算法思维：每步操作必须能安全排除一批候选答案，且不会排除真正的答案。

对于有序数组的两数之和：

  • 和小 → 左指针右移（排除当前行左半部分）
  • 和大 → 右指针左移（排除当前列上半部分）
  • 每步排除至少一行或一列，O(n) 次后搜索空间清空

这个证明框架在后续的三数之和、盛水容器等题目里都能复用，记住它，理解它，就真正掌握了双指针。

编辑此页
最近更新:
贡献者: xiaozhangge