双指针/滑动窗口/前缀和：Maths, CS AI Compendium数组与哈希题型清单-平芜编程栈

双指针/滑动窗口/前缀和：Maths, CS & AI Compendium数组与哈希题型清单

【免费下载链接】maths-cs-ai-compendiumBecome a cracked AI/ML researcher/engineer with this unconventional textbook covering maths, computing, and ML with intuition.项目地址: https://gitcode.com/GitHub_Trending/mat/maths-cs-ai-compendium

在开源教材Maths, CS & AI Compendium的第 14 章《数据结构与算法》中，数组与哈希模块把面试中最值钱的四种题型——双指针、滑动窗口、前缀和、哈希表查找——按"简单 → 中等 → 困难"逐级拆解。本文提炼出完整的题型清单、适用信号和易错点，适合算法面试备考的新手对照练习。

📌 项目简介：一本"直觉优先"的面试备考教材

Maths, CS & AI Compendium 是一本开源、以直觉为先的教科书，从向量、矩阵、微积分一路讲到机器学习、计算机视觉与 ML 系统设计，共 20 章。它的算法章节有一个鲜明主张：教模式，而不是背题解——让你面对没见过的题也能"剥掉背景、认出模式"。

为什么这四种题型值得优先掌握？原文给出了一个直接的判断：

如果你深刻理解数组和哈希表，就能解决大约40% 的编程面试题目。

这两个结构提供了算法最需要的两件事：数组提供 O(1) 的下标访问，哈希表提供 O(1) 的按键查找。foundations.md 中进一步解释：全世界的题目再多，核心模式只有 15–20 个，面试官会不断"换皮"出题，认模式比背答案可靠得多。

🧭 题型总览：四大模式快速对照表

模式	适用信号（什么时候想到它）	代表题型	优化效果
哈希表查找	需要反复问"见过这个值吗？"	两数之和	O(n²) → O(n)
双指针	数组有序 / 需要比较两两配对	三数之和	O(n³) → O(n²)
滑动窗口	满足约束的子串/子数组，且约束单调	最小覆盖子串	O(n²) → O(n)
前缀和	多次范围求和 / 特定和的子数组计数	和为 K 的子数组	O(n²) → O(n)

判断口诀（来自 foundations.md）：

输入有序 → 优先想双指针
子数组/子串 + 单调约束 → 优先想滑动窗口
重复的范围求和查询 → 优先想前缀和
"补数、配对、出现过几次" → 优先想哈希表

1️⃣ 双指针题型清单：两个下标相向而行的 O(n) 解法

双指针用两个下标以相反方向或不同速度扫过数组，前提是数组有序（或排序后不丢失关键信息）。完整讲解见 01. arrays and hashing.md #L166。

难度	题型	核心思路	常见坑
简单	有效回文	左右指针向中间夹逼，跳过非字母数字字符	内层循环漏写`left < right`会越界
中等	三数之和	排序后"固定一个 + 双指针找两数"，总复杂度 O(n²)	去重是最大难点，固定元素和指针结果都要跳过重复值
困难	接雨水	双指针 + 两侧 running max，每次处理较矮的一侧	用`>=`更新最大值，注意 off-by-one

要点记忆：

三数之和（#L200-L239）：i > 0 and nums[i] == nums[i-1]: continue这一行去重逻辑是题眼，漏掉就会输出重复三元组。
接雨水（#L242-L273）：关键洞察是"矮的一侧水深只取决于它自己一侧的 max"，由此做到 O(1) 额外空间，优于预计算左右最大值数组的写法。

2️⃣ 滑动窗口题型清单：先扩张、再收缩的单调区间

滑动窗口维护一个连续区间，right扩张、left收缩，适合"最长/最短满足某条件的子串/子数组"问题——前提是约束是单调的（加元素只会让条件更难或更容易满足，不会两者兼有）。模板与讲解见 #L277-L304。

难度	题型	核心思路	常见坑
简单	买卖股票的最佳时机	退化的窗口：记录历史最低价，每天算一次利润	左指针只在出现新低时前移，别想复杂了
中等	无重复字符的最长子串	哈希表记录字符最近下标，遇重复直接"跳"	必须检查`char_index[char] >= left`，防止用窗口外的旧位置收缩
困难	最小覆盖子串	扩张到覆盖`t`的全部字符，再收缩求最小	`have`计数器让校验 O(1)；比较要用`==`而不是`>=`

要点记忆：

无重复子串（#L326-L350）：用哈希表"跳跃"比用集合逐个删字符更快，这是窗口 + 哈希的经典组合拳。
最小覆盖子串（#L352-L401）：have计数器是决定性优化，没有它每步都要比较整个计数表。
窗口长度公式right - left + 1是最常见的 off-by-one 来源，原文建议"画一个两元素的例子"来核对。

3️⃣ 前缀和题型清单：把 O(n) 区间查询压到 O(1)

前缀和数组满足prefix[i] = sum(arr[0:i])，建一次 O(n)，之后任意区间和sum(arr[l:r]) = prefix[r] - prefix[l]一步取出。讲解见 #L405-L419。

难度	题型	核心思路	常见坑
简单	区间求和查询	O(n) 预处理后，每次查询 O(1)	前缀数组长度是`n + 1`，下标从 0 对齐
中等	和为 K 的子数组	区间和 = 两个前缀和之差 → 用哈希表统计"出现过多少次`prefix - k`"	必须初始化`{0: 1}`，否则漏掉从下标 0 开始的子数组
困难	除自身以外数组的乘积	左趟存前缀积、右趟乘后缀积，全程不做除法	数组含 0 时除法解法直接失效，前缀/后缀法天然免疫

要点记忆：

和为 K 的子数组（#L429-L452）是"前缀和 + 哈希表"双模式叠加的样板题，也是前缀和模式里最常考的中等难度题。
除自身以外乘积（#L454-L482）展示了如何用输出数组本身暂存前缀积，做到 O(1) 额外空间。

4️⃣ 哈希表查找题型清单：O(1) 查找替代 O(n) 扫描

原文建议：只要问题在反复问"见过这个值吗"或"这个键对应什么"，就伸手拿哈希表。完整讲解见 #L76-L77。

难度	题型	核心思路	常见坑
简单	两数之和	遍历一遍，查"补数"是否在表中，查完再插入	先查后插，否则会和自己配对
中等	字母异位词分组	排序后字符串（或 26 维字符计数元组）作为"规范形式"键	Python 列表不可哈希，必须转 tuple
困难	最长连续序列	全体入集合，只从"序列起点"（`num - 1`不在集合）开始数	没有起点判断会退化成 O(n²)

要点记忆：

两数之和（#L80-L100）：单次遍历 + O(1) 查找，总 O(n)；"先检查、后插入"的顺序是这道题唯一的坑。
最长连续序列（#L136-L162）：内层 while 对所有迭代合计最多跑 n 次，所以整体仍是 O(n)——这是面试中常被追问的复杂度论证点。

⚠️ 高频陷阱速查表

原文 Common Pitfalls Summary 总结了这几类题最容易翻车的七个地方：

陷阱	症状	修正
窗口长度 off-by-one	`right - left`与`right - left + 1`混淆	画一个两元素的小例子验证
前缀和漏初始化	漏掉从下标 0 开始的子数组	始终初始化`{0: 1}`
哈希表插入顺序错	两数之和元素自己和自己配对	先查后插
未处理重复	三数之和输出重复三元组	跳过连续相等值
循环里拼接字符串	Python 中`s += c`是 O(n²)	先 append 列表再 join
大数组求和溢出	C++/Java 中 int 溢出	换`long`或检查边界