双指针算法

一、双指针总纲

1.1 双指针四大分类（99% 题目归属）

大类	指针运动方式	本质
① 快慢指针	同向、不同速度	过滤 / 去重 / 找环
② 左右指针	两端向中间对撞	有序数组 + 求和/回文
③ 滑动窗口	同向、窗口伸缩	区间最值（子串/子数组）
④ 多指针	≥3 个指针	排序后枚举（多数求和）

二、① 快慢指针（同向）

2.1 适用场景

• 原地修改数组（删除、去重、移动元素）
• 链表相关（找环、环入口、中间节点）
• 核心特征：指针同方向移动，快指针探路，慢指针记录有效位置

2.2 典型模板

function process(nums) {
  let slow = 0; // 慢指针：记录有效元素的下标
  // 快指针：遍历整个数组，寻找有效元素
  for (let fast = 0; fast < nums.length; fast++) {
    // 满足条件：当前元素有效，保留到慢指针位置
    if (nums[fast] 满足有效条件) {
      nums[slow] = nums[fast];
      slow++; // 慢指针后移，准备接收下一个有效元素
    }
  }
  return slow; // 有效元素的长度
}

2.3 必刷高频题目

题号	题名	核心考点
LC 27	移除元素	有效元素覆盖
LC 26	删除排序数组中的重复项	相邻元素去重
LC 80	删除排序数组中的重复项 II	保留最多两个重复项（slow-2 判断）
LC 283	移动零	非零元素覆盖，末尾补零
LC 141	环形链表	快慢指针追及（判断环）
LC 142	环形链表 II	数学推导 + 环入口定位

三、② 左右指针（对撞指针）

3.1 适用场景

• 有序数组（升序/降序）
• 求和问题（两数之和、三数之和）
• 回文判断、字符串反转、盛水问题
• 核心特征：数组有序，指针从两端向中间收缩，通过调整指针位置逼近目标

3.2 典型模板

function process(nums, target) {
  let left = 0; // 左指针：起始位置
  let right = nums.length - 1; // 右指针：末尾位置

  while (left < right) {
    const cur = 计算当前值（如：nums[left] + nums[right]）;
    if (cur 满足目标条件) {
      // 找到答案，返回或记录
      return [left + 1, right + 1];
    } else if (cur 小于目标) {
      left++; // 左指针右移，增大当前值
    } else {
      right--; // 右指针左移，减小当前值
    }
  }
  return []; // 未找到答案
}

3.3 必刷高频题目

题号	题名	核心考点
LC 167	两数之和 II - 输入有序数组	有序数组求和
LC 15	三数之和	固定一个数 + 左右指针对撞
LC 11	盛最多水的容器	短板效应 + 指针收缩
LC 125	验证回文串	忽略非字母数字 + 回文判断
LC 344	反转字符串	首尾字符交换

四、③ 滑动窗口（同向窗口）

4.1 适用场景

• 连续子串 / 子数组问题
• 求区间最值（最小长度、最大长度、是否存在）
• 核心特征：窗口由左右指针构成（同向移动），右指针扩张窗口，左指针收缩窗口，维护窗口内的合法状态

4.2 典型模板

function process(s/t, target) {
  let left = 0; // 窗口左边界
  let window = {}; // 维护窗口内的状态（如：字符计数、和值）
  let res = 最值初始化; // 如：Infinity（最小长度）、0（最大长度）

  // 右指针扩张窗口，遍历所有元素
  for (let right = 0; right < s.length; right++) {
    const cur = s[right];
    // 更新窗口内状态
    window[cur] = (window[cur] || 0) + 1;

    // 窗口内状态不合法，收缩左指针
    while (窗口不满足合法条件) {
      const leftCur = s[left];
      // 更新窗口内状态
      window[leftCur]--;
      // 左指针右移，收缩窗口
      left++;
    }

    // 更新答案（此时窗口合法）
    res = 取 res 与 当前窗口长度 的最值;
  }

  return res;
}

4.3 必刷高频题目

题号	题名
LC 209	长度最小的子数组
LC 3	无重复字符的最长子串
LC 76	最小覆盖子串
LC 567	字符串的排列
LC 438	找到字符串中所有字母异位词
LC 1004	最大连续1的个数 III

五、④ 多指针（≥3 个）

5.1 适用场景

• 多数求和问题（三数之和、四数之和）
• 排序后枚举所有可能组合
• 核心特征：先排序，再固定前 N-2 个指针，最后两个指针用左右指针对撞

5.2 核心模板（三数之和）

function threeSum(nums) {
  const res = [];
  nums.sort((a, b) => a - b); // 先排序，方便去重和指针移动

  for (let i = 0; i < nums.length; i++) {
    // 去重：跳过重复的固定值
    if (i > 0 && nums[i] === nums[i - 1]) {
      continue;
    }

    let left = i + 1; // 左指针：固定值的下一个元素
    let right = nums.length - 1; // 右指针：数组末尾

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right];
      if (sum === 0) {
        res.push([nums[i], nums[left], nums[right]]);
        // 去重：跳过左指针重复值
        while (left < right && nums[left] === nums[left + 1]) left++;
        // 去重：跳过右指针重复值
        while (left < right && nums[right] === nums[right - 1]) right--;
        // 指针收缩，寻找下一组解
        left++;
        right--;
      } else if (sum < 0) {
        left++;
      } else {
        right--;
      }
    }
  }

  return res;
}

5.3 必刷高频题目

题号	题名
LC 15	三数之和
LC 18	四数之和
LC 16	最接近的三数之和
LC 611	有效三角形的个数

六、双指针与其他算法快速区分

题目特征	优先算法
原地修改数组（删除/去重）	快慢指针
有序数组 + 求和/回文	左右指针
连续区间最值（子串/子数组）	滑动窗口
多数求和（≥3 个数）	多指针
层级遍历 / 最近距离	BFS
所有路径 / 组合排列	DFS + 回溯

七、双指针 10 秒快速判断流程

1. 是否是「连续区间最值」问题（子串/子数组）？→ 是 → 滑动窗口
2. 是否需要「原地删除/覆盖/去重」？→ 是 → 快慢指针
3. 是否是「有序数组 + 求和/回文」？→ 是 → 左右指针
4. 是否是「≥3 个数求和/组合」？→ 是 → 排序 + 多指针
5. 否则 → 考虑其他算法

八、双指针必刷 12 题清单

1. LC 27 移除元素
2. LC 26 删除排序数组中的重复项
3. LC 80 删除排序数组中的重复项 II
4. LC 283 移动零
5. LC 11 盛最多水的容器
6. LC 167 两数之和 II - 输入有序数组
7. LC 15 三数之和
8. LC 3 无重复字符的最长子串
9. LC 76 最小覆盖子串
10. LC 209 长度最小的子数组
11. LC 141 环形链表
12. LC 142 环形链表 II