双指针/滑动窗口/前缀和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-L239i 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-L401have计数器是决定性优化没有它每步都要比较整个计数表。窗口长度公式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-oneright - left与right - left 1混淆画一个两元素的小例子验证前缀和漏初始化漏掉从下标 0 开始的子数组始终初始化{0: 1}哈希表插入顺序错两数之和元素自己和自己配对先查后插未处理重复三数之和输出重复三元组跳过连续相等值循环里拼接字符串Python 中s c是 O(n²)先 append 列表再 join大数组求和溢出C/Java 中 int 溢出换long或检查边界️ 练习路线按顺序过一遍清单模块末尾附了一份按模式分组的 Take-Home 练习清单#L500-L526建议按以下路线学习第 0 步先读 00. foundations.md把 Big O 增长速率表和模式 vs 记忆的思路过一遍第 1 步哈希表查找组两数之和 → 异位词分组 → 最长连续序列第 2 步双指针组回文 → 三数之和 → 接雨水重点练去重第 3 步滑动窗口组股票 → 无重复子串 → 最小覆盖子串先背模板再刷题第 4 步前缀和组区间求和 → 和为 K → 除自身外乘积体会前缀和 哈希表的组合威力。每做完一道对照上文的常见坑列自查一遍比盲目多刷三道更有效。 相关资料核心源码01. arrays and hashing.md数组/哈希原理 四大模式 易错点前置基础00. foundations.mdBig O、递归、回溯、动态规划延伸学习05. sorting and search.md排序与二分双指针题的前置技能项目总览README.md20 章完整目录与学习方法【免费下载链接】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创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考