双指针与滑动窗口
用双指针压缩枚举空间，用滑动窗口维护区间状态。本质都是：少做无效枚举，把 O(n²) 压到 O(n)。代码继续用 JavaScript。
1. 对撞指针
左右两端相向移动，直到相遇。常见于有 序数组或「从两端往中间收」的结构。
// 两数之和（有序）：找一对和为 target 的下标
function twoSumSorted(arr, target) {
let l = 0
let r = arr.length - 1
while (l < r) {
const sum = arr[l] + arr[r]
if (sum === target) return [l, r]
if (sum < target) l++
else r--
}
return [-1, -1]
}
// 原地反转
function reverse(arr) {
let l = 0
let r = arr.length - 1
while (l < r) {
;[arr[l], arr[r]] = [arr[r], arr[l]]
l++
r--
}
return arr
}
// 判断回文
function isPalindrome(s) {
let l = 0
let r = s.length - 1
while (l < r) {
if (s[l] !== s[r]) return false
l++
r--
}
return true
}
移动依据：有序时用「和偏大/偏小」决定动哪边；回文/反转则对称收缩。
2. 快慢指针
两个指针同向，但步进速度不同（或一个走一步、一个走两步）。多用于链表，也可用于数组原地覆盖。
// 链表是否有环（Floyd）
function hasCycle(head) {
let slow = head
let fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
if (slow === fast) return true
}
return false
}
// 找链表中点（快指针走完时，慢指针在中点）
function middleNode(head) {
let slow = head
let fast = head
while (fast && fast.next) {
slow = slow.next
fast = fast.next.next
}
return slow
}
// 数组原地去重（有序）：慢指针写，快指针读
function removeDuplicates(arr) {
if (arr.length === 0) return 0
let slow = 0
for (let fast = 1; fast < arr.length; fast++) {
if (arr[fast] !== arr[slow]) {
slow++
arr[slow] = arr[fast]
}
}
return slow + 1 // 新长度
}
口诀：快的探路，慢的落子（写结果、找中点、判环）。
3. 同向双指针
都从左往右，right 负责扩展，left 在不满足条件时收缩。和滑动窗口高度重合，只是有时不强调「窗口」这个说法。
// 有序数组：平方和不超过 limit 的最长子数组长度
function longestSubarray(arr, limit) {
let left = 0
let sum = 0
let best = 0
for (let right = 0; right < arr.length; right++) {
sum += arr[right]
while (sum > limit) {
sum -= arr[left]
left++
}
best = Math.max(best, right - left + 1)
}
return best
}
何时能用：窗口从 [left, right] 扩到 right+1 后，若仍不合法，只单调地增大 left，不会回头——保证整体 O(n)。
4. 滑动窗口模板
把同向双指针固化成模板：右端推进 → 更新状态 → 左端收缩到合法 → 记录答案。
function slidingWindow(arr) {
let left = 0
// 窗口内状态：计数、和、频次 Map…
const state = initState()
let ans = initAns()
for (let right = 0; right < arr.length; right++) {
add(state, arr[right]) // 右端进窗
while (windowInvalid(state)) {
remove(state, arr[left]) // 左端出窗
left++
}
// 此时 [left, right] 合法，更新答案
ans = update(ans, left, right, state)
}
return ans
}
实现时三件事要对齐：
- 进窗
add/ 出窗remove对称 while收缩条件写对（「不合法就缩」或「仍可缩就缩」）- 答案在缩完之后还是缩之前更新（看题目要最长还是最短）
5. 固定 窗口与可变窗口
固定窗口
窗口长度恒为 k：先填满前 k 个，再右端进一个、左端出一个。
// 定长 k 的最大子数组和
function maxSumFixed(arr, k) {
let sum = 0
for (let i = 0; i < k; i++) sum += arr[i]
let best = sum
for (let i = k; i < arr.length; i++) {
sum += arr[i] - arr[i - k]
best = Math.max(best, sum)
}
return best
}
可变窗口
长度不固定，靠条件伸缩。两种高频问法：
| 问法 | 收缩时机 | 更新答案 |
|---|---|---|
| 最长满足条件的子串/子数组 | 不合法时缩左 | 合法时每次更新 |
| 最短满足条件的子串/子数组 | 已合法时尽量缩左 | 每次合法后更新 |
// 最长：至多包含 k 种字符的子串
function longestKDistinct(s, k) {
const freq = new Map()
let left = 0
let best = 0
for (let right = 0; right < s.length; right++) {
freq.set(s[right], (freq.get(s[right]) || 0) + 1)
while (freq.size > k) {
freq.set(s[left], freq.get(s[left]) - 1)
if (freq.get(s[left]) === 0) freq.delete(s[left])
left++
}
best = Math.max(best, right - left + 1)
}
return best
}
// 最短：和 >= target 的最短子数组
function minSubArrayLen(target, arr) {
let left = 0
let sum = 0
let best = Infinity
for (let right = 0; right < arr.length; right++) {
sum += arr[right]
while (sum >= target) {
best = Math.min(best, right - left + 1)
sum -= arr[left]
left++
}
}
return best === Infinity ? 0 : best
}
6. 典型题型归纳
| 类型 | 指针形态 | 例题直觉 |
|---|---|---|
| 有序两数之和 / 三数之和 | 对撞（+ 定一个枚举） | 和偏大减右，偏小加左 |
| 反转、回文 | 对撞 | 对称收缩 |
| 链表环、中点、第 n 个 | 快慢 | 步长差制造相位差 |
| 原地覆盖、去重、移动零 | 快慢（读写） | 慢指针写结果区 |
| 定长统计 | 固定窗口 | 进一出一 |
| 最长子串/子数组 | 可变窗口 | 不合法才缩 |
| 最短子串/子数组 | 可变窗口 | 合法就尽量缩 |
| 覆盖子串（最小覆盖） | 可变 + 计数欠账 | 缺的字符用 need/欠债计数 |
选型口诀：
- 有序 + 两端关系 → 对撞
- 链表相位 / 原地分区 → 快慢
- 连续子数组/子串 + 单调可维护状态 → 滑动窗口
- 状态不好用加减维护（如任意子序列）→ 窗口未必合适，考虑 DP / 二分等
复杂度：上述模板在 left、right 各自最多走 n 步时，整体 O(n)（另加状态结构的代价，如 Map 的字符集大小）。