文章

【算法】双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书

【算法】双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书 摘要 双指针/滑动窗口系列第一篇，只讲框架不讲题。这个结构本身是一次纠错的结果：我先前按"一题一题做、批改里提炼要点"的方式学这个系列（LC3 写了五版、LC15 四版、LC76 一版过但被拷问），十来道题做完，某天被自己问倒——"双指针的核心原理到底是什么？"竟然答不上来。回溯系列我有"选择、递归、回退"六个字，DP 系列我

发表于
作者 贾永琪
19 分钟阅读
【算法】双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书

文章信息

  • 原文链接：https://jiayq.blog.csdn.net/article/details/164819921
  • 发布时间：2026-09-15 21:41:27
  • 标签：#Golang, #算法, ##开学季·九月创作之星博客挑战赛, ##区间, ##原理

【算法】双指针与滑动窗口（一）：框架总纲——三类问题、一个原理与判决书

摘要

双指针/滑动窗口系列第一篇，只讲框架不讲题 。这个结构本身是一次纠错的结果：我先前按”一题一题做、批改里提炼要点”的方式学这个系列（LC3 写了五版、LC15 四版、LC76 一版过但被拷问），十来道题做完，某天被自己问倒——”双指针的核心原理到底是什么？ “竟然答不上来。回溯系列我有”选择、递归、回退”六个字，DP 系列我有手推表，双指针……只有一堆散落的教训。这篇就是补课：一个统一原理 （被跳过的候选不可能是答案）、三大类地图 （滑动窗口/相向双指针/二分，各自的模板与旋钮）、一份判决书规范 （排除要有论证、幸存者要验明身份）、一套三问流程 （动笔前先答：哪个大类、哪个模板、判决书是什么）。后面三篇按类分篇讲题，题目是框架的例证——先有地图，再上路 。

前置阅读：动态规划第七篇（终章）：单词拆分II——缓存结论的完全体，与两个系列的合龙。配套代码仓库（按题号分目录）：https://github.com/a18792721831/studyleetCode

1. 先认个错：我为什么学得这么狼狈

先交代背景。这个系列开坑前，我刚走完回溯三篇 + DP 七篇，手推表一稿全过的状态。然后 LC3 无重复最长子串连写五版，LC15 三数之和四版，LC76 手推三轮——翻车密度比 DP 后期高出一个数量级 。

当时我归因为”范式切换的成本”，这没错，但只说对了一半。真正的另一半在几个月后做二分系列时才暴露：某天我停下笔问自己”双指针的通用想法是什么”，发现脑子里只有一题一题的碎片——LC3 的哨兵、LC15 的去重宿主、LC76 的三件套——没有一个能统一起来的骨架 。对比之下，回溯我有万能模板（选择-递归-撤销三连），DP 我有五步法和手推表，遇到新题第一反应是”往哪个框架套”。双指针遇到新题，第一反应是”这题是不是又要从零发明”。

病根不在题，在教学顺序：回溯先给模板再做题，DP 由简入繁，而双指针我一直是一题一驱——地图从来没拿到过，只捡了一路的路标。 这篇就是补地图。如果你也在”题目做了不少、原理说不出”的状态，希望这篇能直接把骨架立起来。

2. 一个统一原理

所有双指针/滑动窗口题，不管长什么样，共享一句话：

把 O(n²) 的”枚举所有配对/所有区间”压成 O(n)，压缩的合法性只有一种：证明”被跳过的候选，不可能是答案”。

逐字拆：

  • 候选 ：暴力解里你本该检查的每一对 (i, j) 或每个区间 [l, r]
  • 跳过 ：指针移动时被抛在身后的那一片
  • 证明 ：这是重点——跳过不是省事，是每一步都要携带”被排除者全体无罪”的论证

三个熟悉的化身：LC11 盛水的”谁矮动谁”（矮边的所有剩余配对 ≤ 已记录值）、LC3 滑窗的”left 只进不退”（被跳过的起点配任何终点都不超过已算的答案）、二分的”排除一半”（有序性证明另一半全体 ≠ target）。题型千变万化，压缩的合法性就这一种。

我把这份论证叫做判决书 。它贯穿整个系列，规范有三条：

  1. 排除要有判决书 ：每次动指针，能说出”被排除的为什么不可能是答案”（LC11 的单调性证明是模板）
  2. 幸存者要验明身份 ：循环退出时指针停在哪、那格是什么语义、是不是答案——三问缺一不可（LC35 的 return l 靠的是”l 左侧全 < target”这份汇总判决；LC34 忘了验 nums[l] != target 就输出垃圾）
  3. 买不到信息就退化 ：论证不了排除，就只能缩小一格（LC81 的 l++——等值遮住断崖时，唯一安全的动作是扔掉一个已知非答案的格子）

3. 三门技术是一家

用”核心对象 + 核心动作”给三门算法对仗，双指针的位置立刻清晰：

核心对象核心动作一句话 
回溯路径 （path）选择、递归、回退决策树上走路，走了要退
DP状态表 （dp 数组）递推格子由格子算出来
双指针区间 （窗口）吃进、判定、吐出两端夹逼一个区间，每步只动一个端点

回溯的合法性靠”回退还原”，DP 靠”无后效性”，双指针靠指针永不回头 ——而它的底气就是第 2 节的判决书。

三门还有一条演化关系（DP 终章写过前半）：回溯是决策树上走路，DP 是把树折叠成表。补上后半句——

双指针是折叠的极限：当状态简单到一个区间就能描述，DP 的整张表退化成两个下标。

LC3 亲眼见过这个退化：dp[i] = i - left + 1，dp 数组蒸发，剩下 l 和 r 两个变量。所以双指针不是新世界，是 DP 的特例——窗口足够简单，表就缩成了指针 。这个视角的实用价值：遇到新题先问”这题的状态能不能用一个区间描述”——能，滑窗；状态更复杂，回 DP。

4. 三大类地图

4.1 大类一：滑动窗口（同向双指针）

识别信号 ：连续子串/子数组 + 窗口性质可增量维护（无重复/和/覆盖计数）。

1
2
3
4
5
6
7
8
9
10

l = 0
for r := 0; r < n; r++ {
    进：window 加入 s[r]，维护状态
    for 收缩条件 {              ← 旋钮一
        出：window 移除 s[l]，维护状态
        l++
    }
    记录答案                    ← 旋钮二
}

模板固定，每题只调两个旋钮：

题型收缩条件记录时机例题
求最长窗口不合法时收缩（恢复合法）每轮扩张后LC3 无重复最长子串
求最短窗口合法时收缩（收缩即产出 ，每格是候选）收缩循环内LC209 最短子数组 / LC76 最小覆盖

状态形态每题不同（一张计数表 / 一个和 / need-window-count 三件套），但纪律恒定：吃进动了什么账，吐出就销什么账 ——进出各维护一次，缺半个就是 bug。

4.2 大类二：相向双指针

识别信号 ：排序后 找配对（两数之和 / 三数之和 / 区间极值）。

1
2
3
4
5
6

l, r = 两端
for l < r {
    用有序性做一次 O(1) 比较 → 排除一整排候选
    只动一个指针
}

比较的两种典型：和与 target 比（LC167 两数之和：和大 r–、和小 l++）、端点值互比（LC11 盛水：谁矮动谁）。一轮只动一个指针、动作互斥 ——我在这上面栽过著名的”平行 if 无互斥”四连犯（LC3 的三参数 max、LC15 的六 if 递归、LC33 的双 if 判定、LC81 的混搭收缩），症状全是同一轮指针走多条路。铁律：指针一轮一步。

4.3 大类三：二分

识别信号 ：有序 + 单点查询或找边界，O(log n) 硬要求。

两类模板，先分清再动笔：

1
2
3

找点：  for l <= r { mid; 判定; mid±1 }        ← == 是终点，mid 出局
找边界：for l < r  { mid; 判定; 保 mid 收缩 }   ← == 是路标，mid 可能是答案

三条铁律：

  1. 循环条件与收缩方式配对 ：l<=r ↔ mid±1；l<r ↔ r=mid（保 mid）。拆开单换一个，就是”最后一格永不检查”或”l==r 死循环”
  2. 值域两端都要卡 ：有序半是个闭区间，判定写 nums[l] <= target && target < nums[mid]——mid 端开着（判过 == 已出局），l/r 端闭着（还没判过，必须留在候选里）。只写 mid 一端是我犯过三次的病 （见第 6 节）
  3. 判定锚点要无歧义 ：LC153 找最小值锚点是 nums[r] 而非 nums[l]（后者在未旋转数组上有歧义）；LC33 判哪半有序锚点是 nums[l] vs nums[mid]（配 <=，让 l==mid 的退化情况走对分支）

4.4 大类之间的暗门

  • LC15 三数之和 = 固定一个数 + 内层相向双指针（大类二嵌套）
  • LC33/153/81 旋转数组 = 二分 + 变化的判定设计（锚点选择 / 哪半有序 / 等值退化）
  • LC3 从 DP 走到滑窗 = 表退化成指针（第 3 节的演化关系）

5. 三问流程（动笔前，答案写注释第一行）

1
2
3
4

1. 哪个大类？（滑窗 / 相向 / 二分）
2. 哪个模板、哪个旋钮？（两类模板 / 收缩条件 / 判定锚点）
3. 判决书是什么？（排除的合法性；循环退出时幸存者的身份）

实测过的价值：重做阶段用这套流程，上次的病三次都在纸面上现形、没进代码 ——LC33 重做的三问答到一半，”值域判断又只剩半边”当场被抓住（首次做时这个病是靠七个用例实测才暴露的）。三问的成本是两分钟，省的是一整轮提交-翻车-修复。

6. 我的翻车史挂回框架（自用检查表）

坑框架位置一句话
LC3 断链套收缩、used 清空大类一收缩是挤掉一头，不是推倒重来
LC76 跳跃收缩、答案在表里消失大类一最短型收缩即产出，每格是候选，手推表不许一笔带过
LC15 六 if 递归、元素复用大类二一轮只动一个指针，互斥
LC33 找点模板套找边界题大类三先问 mid 可不可以出局
LC81 重发明丢值域两端、丢守卫大类三改代码用加法不用重写；旧版的守卫是血换的
LC34 值域半边（三犯）大类三排除式思维总漏端点——改用包含式：在不在值域里，两端都卡
平行 if 无互斥（四犯）全类指针一轮一步
l=mid 死循环大类三l 方向收缩只能配 mid+1（mid 向下取整偏向 l）

7. 框架生效的实证

同一批题，首次做 vs 带框架重做：

题首次重做
LC34三版（线性扩张 → 死循环嵌套死代码 → 终版）两版（核心一步到位，只丢一个守卫）
LC33两版（七用例七错起步）思考题抓病 + 一版全绿
LC153两版（模板错配出恒假条件）一版全绿

数据说话：坑没有白踩，但坑要挂到框架的钩子上才算资产 ——散着放，它们只是挫折；挂起来，它们是检查表的行。

总结

这篇没有一道题的完整题解，只有三样东西：一个原理 （被跳过的候选不可能是答案——压缩合法性的唯一来源）、一张地图 （三大类，各自的对象/动作/模板/旋钮/铁律）、一套纪律 （三问流程 + 判决书三条规范）。

感触最深的一点写在这里：我此前把”会做题”当成目标，于是用题量堆熟练度；这个系列的教训是没有框架的题量只是翻车史的长短 。回溯六个字能统领十一道题，DP 一张表能统领六级——双指针的”六个字”我现在有了：吃进、判定、吐出；比较、排除、收缩 。后面三篇按类讲题，每题都是这张地图上的一次点名。

下一篇：滑动窗口——吃进、判定、吐出，从 LC209 最短子数组开始。

参考资料

版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。

Golang, 算法, 开学季·九月创作之星博客挑战赛, 区间, 原理
本文由作者按照 CC BY 4.0 进行授权