寻北

Appearance

双指针技巧 (Two Pointers) ​

1. 双指针核心概览 ​

双指针并不是一种具体的“算法”（如排序或 DFS），而是一种编程技巧。它的核心思想是：在遍历数组、字符串或链表时，不再使用单一的变量 i 去循环，而是同时维护两个指向不同位置的索引（指针），通过它们之间的协同移动来完成特定的搜索、比较或原地修改操作。

1.1 双指针的四大黄金应用模型 ​

掌握双指针，本质上是掌握它在不同场景下的移动轨迹。绝大多数双指针问题都可以归类为以下四种模型：

模型分类指针初始位置移动轨迹与特征典型应用场景
对撞指针 (左右指针)一左一右 (left=0, right=len-1)两人相向而行，直到相遇 (left >= right) 停止。反转字符串、回文串判定、有序数组求和/二分查找。
快慢指针同一起点 (fast=0, slow=0)两人同向而行，快指针探路，慢指针在后方记录或修改数据。数组原地去重、移除元素、链表找中点/判断环。
滑动窗口同一起点 (left=0, right=0)同向而行。右指针主动扩张窗口，左指针在满足条件时收缩窗口。求满足特定条件的连续子数组/子串（最长/最短）。
双数组指针分别在两个数组的起点根据比较结果，各自独立移动。合并两个有序数组、求两个数组的交集。

2. 经典双指针模型与 JavaScript 实现 ​

2.1 对撞指针：两数之和 II (有序数组) ​

题目描述： 给你一个下标从 1 开始的整数数组 numbers，该数组已按非递减顺序排列。请你从数组中找出满足相加之和等于目标数 target 的两个数。 （如果是无序数组，应该用哈希表；但既然是有序的，双指针是空间复杂度 $O(1)$ 的最优解）。

核心逻辑： 既然数组是有序的，左指针指向最小的数，右指针指向最大的数。 如果两数之和大了，说明右边的数太大了，右指针左移（变小）；如果和太小，左指针右移（变大）。

JavaScript 代码实现 ​

js
/**
 * 两数之和 II - 对撞指针
 * @param {number[]} numbers (已排序)
 * @param {number} target
 * @return {number[]}
 */
function twoSum(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) { // 不能等于，因为要找的是两个不同的数
        const sum = numbers[left] + numbers[right];
        
        if (sum === target) {
            // 题目要求下标从 1 开始，所以加 1
            return [left + 1, right + 1];
        } else if (sum < target) {
            left++; // 和太小，左边的指针往右走（找更大的数）
        } else {
            right--; // 和太大，右边的指针往左走（找更小的数）
        }
    }
    return [];
}

2.2 快慢指针：原地移除元素 (Remove Element) ​

题目描述： 给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素，并返回移除后数组的新长度。不能使用额外的数组空间。

核心逻辑： fast 指针负责在前面“探路”扫描整个数组，slow 指针负责在后面“驻扎”，只记录那些不等于 val 的有效元素。

JavaScript 代码实现 ​

js
/**
 * 原地移除元素 - 快慢指针
 * @param {number[]} nums
 * @param {number} val
 * @return {number} 新数组的长度
 */
function removeElement(nums, val) {
    let slow = 0; // 慢指针：指向下一个即将被合法元素覆盖的位置

    // 快指针：负责遍历所有元素
    for (let fast = 0; fast < nums.length; fast++) {
        // 只有当快指针找到“有效元素”时，才把它交接给慢指针
        if (nums[fast] !== val) {
            nums[slow] = nums[fast]; // 覆盖
            slow++; // 慢指针前进一步
        }
        // 如果 nums[fast] === val，快指针直接跳过，慢指针原地待命
    }
    
    // 最终 slow 的值恰好就是有效元素的个数
    return slow;
}

3. 常见问题深度剖析 (FAQ) ​

常见疑惑深度解析与应对策略
1. 怎么判断一道题到底是用“对撞指针”还是“同向指针”？🔹 对撞（左右）指针的暗号： 题目中有**“有序数组”（如两数之和）、“反转/回文”（从两头向中间靠拢）、“面积/盛水”（如接雨水题）。
🔹 同向（快慢/滑动窗口）的暗号： 题目要求“原地修改/去重”、求“连续的子数组/子串”**。
2. 双指针的时间复杂度真的是 $O(n)$ 吗？通常是的，但要小心隐性循环。 比如对撞指针，左右指针总共把数组走了一遍，绝对是 $O(n)$。再看上面的“滑动窗口”代码，里面嵌套了一个 while 循环，看起来像 $O(n^2)$。错！ 虽然有两层循环，但不管是 right 还是 left，它们都只前进，绝不后退（即不走回头路）。所以每个字符最多被 right 访问一次，被 left 踢出一次，总操作次数最多是 $2n$，去掉常数后依然是严格的 $O(n)$。
3. JavaScript 中字符串是不可变的 (Immutable)，怎么用双指针进行“原地反转”？这是 JS 新手极易踩坑的地方。在 C++ 或 Java 中，你可以直接操作 str[left] = str[right]。但在 JS 中，字符串的字符是只读的，无法直接原地修改。
解决方案： 必须先将字符串打散成数组 let arr = s.split('');，在数组上用双指针完成交换操作后，再重新拼接 return arr.join('');。虽然这消耗了 $O(n)$ 的空间，但在 JS 中这是唯一标准的做法。
4. 双指针和链表结合时要注意什么？在单向链表中，不可能使用对撞（左右）指针，因为链表不能从后往前遍历。链表双指针永远是快慢指针。最经典的应用是：找链表的中点（快指针走两步，慢指针走一步，快指针到底时慢指针正好在中点）、判断链表是否有环（龟兔赛跑，如果快慢指针相遇，说明有环）。