对撞指针入门：有序数组中的两数之和

摘要

对撞指针是最容易上手的双指针模型：两个指针从数组两端出发，根据当前两端的和与目标值的大小关系，决定哪一端内缩。本文从 Two Sum II 出发，严格证明对撞指针的正确性（为什么每次移动不会错过答案），然后推广到 Valid Palindrome 和 Reverse String，揭示对撞指针在”从两端向中间消解”问题中的统一模式。

第 1 章问题引入：无序版 Two Sum 的局限

1.1 LeetCode 1 vs LeetCode 167

LeetCode 1（Two Sum）和 LeetCode 167（Two Sum II）看起来极其相似，但有一个关键差别：

	LeetCode 1（Two Sum）	LeetCode 167（Two Sum II）
输入	无序数组	升序数组（保证有序）
返回	下标（0-indexed）	下标（1-indexed）
标准解法	哈希表， $O (n)$ 时间， $O (n)$ 空间	对撞指针， $O (n)$ 时间， $O (1)$ 空间

LeetCode 1 用哈希表：扫描数组，对每个元素 x，检查 target - x 是否在哈希表中，不在则将 x 加入哈希表。时间 $O (n)$ ，但空间 $O (n)$ 。

LeetCode 167 的输入已经有序，这个额外的保证让我们可以用 $O (1)$ 空间的对撞指针。有序性才是对撞指针的关键，不是题目本身。

1.2 为什么有序才能用对撞指针

先看一个对比实验。给无序数组 [3, 1, 4, 2]，target = 5，从两端出发：

left=0(3), right=3(2)，和为 5，返回。（巧合正确）

再看 [3, 1, 4, 2]，target = 3：

left=0(3), right=3(2)，和为 5 > 3，right--
left=0(3), right=2(4)，和为 7 > 3，right--
left=0(3), right=1(1)，和为 4 > 3，right--
left=0(3), right=0，left == right，循环结束，输出”无解”

但实际上 nums[1] + nums[3] = 1 + 2 = 3 是有解的！对撞指针在无序数组上直接失效。

失效的根本原因：在无序数组中，right-- 之后新的 nums[right] 不一定更小，“和偏大就缩小右端”的推论失去依据。

第 2 章 LeetCode 167：两数之和 II

2.1 题目

LeetCode 167 - Two Sum II - Input Array Is Sorted（中等）

给你一个下标从 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。

输入：numbers = [2,3,4], target = 6
输出：[1,3]

输入：numbers = [−1,0], target = −1
输出：[1,2]

2.2 对撞指针解法

public int[] twoSum(int[] numbers, int target) {
    int left = 0, right = numbers.length - 1;
 
    while (left < right) {
        int sum = numbers[left] + numbers[right];
 
        if (sum == target) {
            return new int[]{left + 1, right + 1};  // 转换为 1-indexed
        } else if (sum < target) {
            left++;   // 和偏小，左指针右移，换一个更大的数
        } else {
            right--;  // 和偏大，右指针左移，换一个更小的数
        }
    }
 
    return new int[]{-1, -1};  // 题目保证有解，实际不会到这里
}

时间复杂度： $O (n)$ ；空间复杂度： $O (1)$ 。

代码极简，但其正确性需要严格证明。

2.3 正确性证明：为什么对撞指针不会错过答案？

这是面试中常被追问的关键问题。直觉上很明显，但能说清楚证明过程的人并不多。

命题：若数组中存在下标对 $(i^{*}, j^{*})$ （ $i^{*} < j^{*}$ ）满足 numbers[i*] + numbers[j*] == target，对撞指针算法一定能找到它（或找到另一个合法的答案对）。

证明（反证法）：

假设对撞指针在某步执行了 left++（即从 left 移到 left+1），此时 left == l，right == r，且 numbers[l] + numbers[r] < target。

我们想证明：此步操作不会错过以 l 为左端点的任何解。

由于数组有序， $r^{'} \leq r$ 时 numbers[l] + numbers[r'] ≤ numbers[l] + numbers[r] < target。因此，以 l 为左端点、任意 $j \leq r$ 为右端点的所有组合，和都小于 target，都不是解。

对撞指针在执行 left++ 之前，right 是当前最大的右端点 $r$ ；以 $l$ 为左端点的所有可能右端点（包括 $r$ 在内所有更小的右端点）的和都 $< target$ 。因此，以 $l$ 为左端点的所有对都不是解，可以安全地将 l 排除，即 left++。

对称地，若 numbers[l] + numbers[r] > target，则对任意 $i \geq l$ ，numbers[i] + numbers[r] >= numbers[l] + numbers[r] > target，以 $r$ 为右端点的所有对也都不是解，可以安全 right--。

结论：每次 left++ 或 right-- 都排除了当前左端或右端的所有合法组合，不遗漏任何解。 $□$

核心概念：排除的逻辑是行/列级别的

left++ 排除的是”以当前 left 为左端点的所有可能右端点”（整行）；right-- 排除的是”以当前 right 为右端点的所有可能左端点”（整列）。两种操作合计排除量 $O (n)$ ，而指针总移动步数也是 $O (n)$ ，因此时间复杂度是 $O (n)$ 。

2.4 边界条件分析

边界一：while (left < right) 还是 while (left <= right)？

题目要求两个数的下标不同（index1 < index2），所以 left 和 right 不能相等。用 left < right 确保循环内 left != right，自然避免”同一个元素用两次”的问题。

边界二：数组中存在负数时是否影响正确性？

不影响。对撞指针的正确性证明只依赖”数组有序”，不要求元素为正数。负数完全可以处理，如样例 [-1, 0]，target = -1。

边界三：只有两个元素时

left = 0，right = 1，直接检查 numbers[0] + numbers[1]，正好等于 target 就返回 [1, 2]，否则退出循环（因为 left < right 不成立）。题目保证有解，所以不会走到返回 -1 的分支。

第 3 章 LeetCode 125：验证回文串

3.1 题目

LeetCode 125 - Valid Palindrome（简单）

如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样，则可以认为该短语是一个 回文串。

字母和数字都属于字母数字字符。

给你一个字符串 s，如果它是 回文串，返回 true；否则，返回 false。

输入: s = "A man, a plan, a canal: Panama"
输出：true
解释："amanaplanacanalpanama" 是回文串。

输入：s = "race a car"
输出：false

输入：s = " "
输出：true
解释：在移除非字母数字字符之后，s 是一个空字符串 ""。空字符串正着反着读都一样，所以是回文串。

3.2 解题思路

回文判断是对撞指针的另一个经典场景。两个指针从两端出发，依次向中间移动，比较字符是否相等。

本题的额外挑战是：需要忽略非字母数字字符和大小写。处理策略：

left 从左向右跳过非字母数字字符
right 从右向左跳过非字母数字字符
双方都停下来之后，比较字符（忽略大小写）
不相等则返回 false；相等则继续

public boolean isPalindrome(String s) {
    int left = 0, right = s.length() - 1;
 
    while (left < right) {
        // 左指针跳过非字母数字字符
        while (left < right && !Character.isLetterOrDigit(s.charAt(left))) {
            left++;
        }
        // 右指针跳过非字母数字字符
        while (left < right && !Character.isLetterOrDigit(s.charAt(right))) {
            right--;
        }
 
        // 比较（忽略大小写）
        if (Character.toLowerCase(s.charAt(left)) != Character.toLowerCase(s.charAt(right))) {
            return false;
        }
        left++;
        right--;
    }
    return true;
}

时间复杂度： $O (n)$ ，每个字符最多被访问两次（一次被跳过，一次被比较）。 空间复杂度： $O (1)$ ，原地操作，不需要先构造去除非字母数字字符后的新字符串。

3.3 为什么不先预处理字符串再判断？

另一种思路：先用一次遍历过滤出字母数字字符，构造新字符串 filtered，再直接比较 filtered 与 filtered.reverse()。

这个思路完全正确，但空间复杂度是 $O (n)$ （新字符串）。对撞指针的优势正是 $O (1)$ 空间——直接在原字符串上操作。

在空间敏感的场景（如处理超大字符串流）下， $O (1)$ 空间的对撞指针明显优于 $O (n)$ 空间的预处理方案。

3.4 边界条件分析

边界一：空字符串或全是非字母数字字符

如 s = " "，左右跳过非字母数字字符后 left >= right，循环不进入，返回 true。这符合题意（空字符串是回文）。

边界二：内层 while 的边界

while (left < right && ...) 中的 left < right 判断不能省略。假设字符串全是非字母数字字符（如 "!!!"），如果不判断 left < right，左指针会一直向右越界。

边界三：奇数长度字符串

如 "aba"，left=0(a), right=2(a) 相等，left=1, right=1，left < right 为假，退出循环，返回 true。中间的字符 b 不需要判断，正确。

第 4 章 LeetCode 344：反转字符串

4.1 题目

LeetCode 344 - Reverse String（简单）

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组，使用 $O (1)$ 的额外空间解决这一问题。

输入：s = ['h','e','l','l','o']
输出：['o','l','l','e','h']

输入：s = ['H','a','n','n','a','h']
输出：['h','a','n','n','a','H']

4.2 解法

反转字符串是对撞指针最基础的应用：两个指针从两端出发，交换元素，相向移动。

public void reverseString(char[] s) {
    int left = 0, right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        left++;
        right--;
    }
}

这道题本身足够简单，但它揭示了对撞指针的原型操作：“从两端操作，向中间收缩”。

4.3 从反转到回文：统一的视角

反转字符串和判断回文，本质上是同一个对撞指针框架：

操作	反转字符串	判断回文
初始化	`left=0, right=n-1`	`left=0, right=n-1`
每次操作	交换 `s[left]` 和 `s[right]`	比较 `s[left]` 和 `s[right]`
终止条件	`left >= right`	`left >= right` 或不相等

理解了这个统一框架，遇到”从两端向中间处理”的问题，首先想到对撞指针。

第 5 章变体：有序数组的其他对撞指针问题

5.1 平方后有序数组（LeetCode 977）

LeetCode 977 - Squares of a Sorted Array（简单）

给你一个按 非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]

直觉：平方后，原来的最大正数和最小负数（绝对值最大的负数）的平方是最大的，即”最大的平方在两端”。用对撞指针从两端取较大的平方，填入结果数组（从后往前填）。

public int[] sortedSquares(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    int left = 0, right = n - 1;
    int pos = n - 1;  // 从结果数组末尾开始填
 
    while (left <= right) {
        int leftSq = nums[left] * nums[left];
        int rightSq = nums[right] * nums[right];
        if (leftSq > rightSq) {
            result[pos--] = leftSq;
            left++;
        } else {
            result[pos--] = rightSq;
            right--;
        }
    }
    return result;
}

时间复杂度： $O (n)$ （比先平方再排序的 $O (n lo g n)$ 更优）。

这道题的特别之处在于：对撞指针的”单调性”来源不是”和偏大则收缩右端”，而是”平方值在两端最大，从两端取较大值”。不同的单调性，相同的框架。

5.2 移动零（LeetCode 283）

LeetCode 283 - Move Zeroes（简单）

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

这道题通常用同向双指针（也叫快慢指针在数组上的应用）：slow 指向下一个应该填写非零元素的位置，fast 扫描数组找非零元素。

public void moveZeroes(int[] nums) {
    int slow = 0;  // 指向下一个应该填写非零元素的位置
    for (int fast = 0; fast < nums.length; fast++) {
        if (nums[fast] != 0) {
            // 将非零元素放到 slow 位置
            int temp = nums[slow];
            nums[slow] = nums[fast];
            nums[fast] = temp;
            slow++;
        }
    }
}

注意这里不是对撞指针，而是同向双指针（slow 和 fast 都从左向右）。但其核心思路依然是”fast 扫描，slow 维护结果区间”。

这提示了一个重要的模式：双指针不一定要从两端出发，“同向双指针”在原地去重/过滤类问题中同样常用。

第 6 章对撞指针的核心边界总结

6.1 三个必须确认的边界条件

使用对撞指针时，以下三个问题必须在写代码前想清楚：

问题一：循环条件是 left < right 还是 left <= right？

找两个不同位置的元素：用 left < right，避免同一元素使用两次
两端向中间消解（如反转字符串）：用 left < right，奇数长度时中间元素不需处理
特殊情况下 left == right 也需要处理：用 left <= right（较少见）

问题二：循环体内移动指针后是否需要 continue？

在 Two Sum II 中，找到答案后直接 return，不需要 continue。但如果有重复元素需要去重（如 3Sum），找到答案后还需要跳过重复元素再继续循环，逻辑更复杂（详见下一篇）。

问题三：输入数组是否保证非空？

numbers.length >= 2 是 Two Sum II 的题目保证，如果输入可能为空或只有一个元素，需要额外的边界检查。面试中主动询问或添加防御性判断。

6.2 常见错误模式

错误一：在无序数组上直接用对撞指针

未经排序的数组不具备全局有序性，对撞指针的正确性证明失效，会产生错误答案。解决方案：先排序（ $O (n lo g n)$ ），再用对撞指针。

错误二：漏了”跳过非合法字符”的内层循环边界

在 Valid Palindrome 中，内层 while 跳过非字母数字字符时，必须同时判断 left < right，否则在全非字母数字字符的字符串上会越界。

错误三：返回值是 1-indexed 时忘记 +1

Two Sum II 要求返回 1-indexed 下标，忘记 +1 是常见的低级错误。写代码时用注释标注清楚。

小结

对撞指针的精髓可以用一句话概括：利用有序性，每次移动一端，永久消除以当前端点为左/右端点的所有组合。

这篇文章覆盖了三道题：

Two Sum II：最标准的对撞指针模板，含正确性证明
Valid Palindrome：对撞指针结合字符过滤，注意内层循环边界
Reverse String：对撞指针最基础的原型操作

下一篇将把对撞指针推广到三个数甚至四个数的情形（3Sum、4Sum），核心思路是固定最外层循环，把多数之和问题逐步降维为两数之和问题。去重逻辑是那里最需要仔细处理的细节。

汀的知识碎片

文章导航

02 对撞指针入门：有序数组中的两数之和

对撞指针入门：有序数组中的两数之和

摘要

第 1 章问题引入：无序版 Two Sum 的局限

1.1 LeetCode 1 vs LeetCode 167

1.2 为什么有序才能用对撞指针

第 2 章 LeetCode 167：两数之和 II

2.1 题目

2.2 对撞指针解法

2.3 正确性证明：为什么对撞指针不会错过答案？

2.4 边界条件分析

第 3 章 LeetCode 125：验证回文串

3.1 题目

3.2 解题思路

3.3 为什么不先预处理字符串再判断？

3.4 边界条件分析

第 4 章 LeetCode 344：反转字符串

4.1 题目

4.2 解法

4.3 从反转到回文：统一的视角

第 5 章变体：有序数组的其他对撞指针问题

5.1 平方后有序数组（LeetCode 977）

5.2 移动零（LeetCode 283）

第 6 章对撞指针的核心边界总结

6.1 三个必须确认的边界条件

6.2 常见错误模式

小结

On this page

汀的知识碎片

文章导航

02 对撞指针入门：有序数组中的两数之和

对撞指针入门：有序数组中的两数之和

摘要

第 1 章 问题引入：无序版 Two Sum 的局限

1.1 LeetCode 1 vs LeetCode 167

1.2 为什么有序才能用对撞指针

第 2 章 LeetCode 167：两数之和 II

2.1 题目

2.2 对撞指针解法

2.3 正确性证明：为什么对撞指针不会错过答案？

2.4 边界条件分析

第 3 章 LeetCode 125：验证回文串

3.1 题目

3.2 解题思路

3.3 为什么不先预处理字符串再判断？

3.4 边界条件分析

第 4 章 LeetCode 344：反转字符串

4.1 题目

4.2 解法

4.3 从反转到回文：统一的视角

第 5 章 变体：有序数组的其他对撞指针问题

5.1 平方后有序数组（LeetCode 977）

5.2 移动零（LeetCode 283）

第 6 章 对撞指针的核心边界总结

6.1 三个必须确认的边界条件

6.2 常见错误模式

小结

On this page

第 1 章问题引入：无序版 Two Sum 的局限

第 5 章变体：有序数组的其他对撞指针问题

第 6 章对撞指针的核心边界总结