Hot100 思维难点与注意事项
Hot100 思维难点与注意事项 [!info] 目的 记录 Hot100 刷题中的思维卡点、易错点和复盘结论，方便后续回看和查漏补缺。 关联：[[Algorithm/_index|算法目录]] 记录模板 题目：`` 日期： 难点类型：（状态定义 / 边界处理 / 数据结构选择 / 复杂度优化 / 代码实现） 卡住原因： 关键突破： 注意事项： 一句话复盘： 条目记录 哈希表类题目（两数之和 / 字母异位词分组 / 最长连续序列） 日期：2026-03-02 难点类型：数据结构选择 / 复杂度优化 核心共性：能用哈希把“重复查找、归类、存在性判断”从线性扫描降为常数级查找。 典型题目： 两数之和：用 值 -> 下标 的映射，把配对查找优化到 O(n)。 字母异位词分组：构造稳定且唯一的哈希键（排序串或字符计数）完成分组。 最长连续序列：用哈希集合做存在性判断，只从“序列起点”扩展，避免重复遍历。 注意事项： 哈希题先想 key 的定义是否唯一、稳定、可快速计算。 两数之和一般先查后存，避免同一元素被重复使用。 最长连续序列避免从每个元素都向后遍历，否则会退化到 O(n^2)。 一句话复盘：哈希表题的本质是先建索引，再用常数时间查询或分组来换时间复杂度。 双指针类题目（移动零） 日期：2026-03-02 难点类型：指针语义 / 原地修改 核心共性：快指针负责扫描并找有效值，慢指针负责维护“已处理区间”的正确位置。 典型思路： 快指针遍历数组，遇到非 0 元素就写到慢指针位置。 每次写入后慢指针后移一位。 快指针结束后，把慢指针到数组末尾的元素全部补为 0。 注意事项： 先覆盖非 0，再统一补 0，逻辑最稳定。 这是原地算法，时间复杂度 O(n)，额外空间复杂度 O(1)。 不要在遍历时频繁交换或删除元素，容易引入额外复杂度和边界错误。 一句话复盘：移动零的关键是职责分离，快指针找值，慢指针定位置。 双指针类题目（盛最多水的容器） 日期：2026-03-02 难点类型：贪心策略 / 指针移动规则 核心思路：左右指针从两端向中间逼近，每一步计算面积并维护最大值。 关键突破：每次移动较短的一侧，才有机会让最短边变大；移动较长边通常不会得到更优解。 注意事项： 面积公式：(right - left) * min(height[left], height[right])。 遍历过程中持续更新最大面积即可，时间复杂度 O(n)，空间复杂度 O(1)。 一句话复盘：这题本质是“边收缩边取最优”，重点在于正确的指针移动策略。 双指针类题目（三数之和） 日期：2026-03-02 难点类型：去重策略 / 指针配合 核心思路：先固定第一个数，再用左右指针在剩余区间内逼近寻找另外两个数。 关键突破：这题正确性的关键不是只找到答案，而是系统地去重避免重复三元组。 注意事项： 先排序，再进行双指针，便于逼近和去重。 固定第一个数 i 时，若 nums[i] == nums[i-1] 则跳过。 当 left + right 与目标值配对成功后，左右指针都要跳过连续相同值，再继续移动。 时间复杂度 O(n^2)，空间复杂度通常为 O(1)（不计输出）。 一句话复盘：三数之和是“固定一个数 + 双指针”，难点在完整且不漏解的去重流程。 多解法题目（接雨水） 日期：2026-03-02 难点类型：状态定义 / 边界处理 / 数据结构选择 核心共性：每个位置可接雨水量由 min(左侧最高, 右侧最高) - 当前高度 决定。 方案 1（前后缀最大值）： 预处理 leftMax[i] 和 rightMax[i]，再线性遍历累加每个位置雨水量。 时间复杂度 O(n)，空间复杂度 O(n)。 方案 2（双指针）： 左右指针向中间收缩，同时维护 leftMax 和 rightMax。 每次由较低一侧确定当前可接雨水并移动该侧指针。 时间复杂度 O(n)，空间复杂度 O(1)。 方案 3（单调栈）： 用单调递减栈保存下标，当前高度大于栈顶时弹栈并计算“凹槽”积水。 计算时要注意宽度为 right - left - 1，高度为 min(height[left], height[right]) - height[bottom]。 时间复杂度 O(n)，空间复杂度 O(n)。 注意事项： 单调栈里建议存下标而不是高度，方便同时计算宽度和高度差。 双指针法的核心不是盲目比较两端值，而是基于当前 leftMax/rightMax 判断哪一侧可确定。 一句话复盘：接雨水是一题多解，但本质都在求每个位置两侧“挡板下界”。 滑动窗口类题目（无重复字符的最长子串） 日期：2026-03-02 难点类型：窗口维护 / 指针移动规则 核心思路：可视作快慢指针。fast 负责扩张窗口，遇到重复字符时 slow 前移并逐步移出元素，直到窗口重新满足“无重复”。 关键突破：窗口始终保持“当前区间无重复”，每次扩张后更新最大长度。 注意事项： Go 中可用 map[byte]struct{} 充当字符集合（若题目仅含 ASCII）。 删除窗口左端字符使用 delete(hash, s[slow])，再移动 slow。 当字符串可能包含多字节字符时，需改用 rune 处理，避免按字节切分出错。 时间复杂度 O(n)，空间复杂度 O(字符集大小)。 一句话复盘：这题本质是动态维护一个“合法窗口”，重复就缩窗，不重复就扩窗。 滑动窗口类题目（找到字符串中所有字母异位词） 日期：2026-03-02 难点类型：定长窗口 / 状态维护 核心思路：这是定长滑动窗口。窗口每右移一格，就执行“新字符计数 +1、旧字符计数 -1”，再判断当前窗口是否匹配。 关键突破：窗口长度固定为 len(p)，所以不需要像可变窗口那样反复缩窗，按节奏推进即可。 实现体会： 可用 map 做计数，也可用定长数组（如 [26]int）做计数；你这题用数组是合理且常见的优化。 若“差值计数表”所有值都为 0，说明当前窗口与 p 字符频次一致，记录左边界索引。 注意事项： if i-len(p)+1 < 0 { continue } 这段表示窗口还没形成完整长度，属于预热阶段，不进入通用匹配流程。 记录答案时索引是窗口左端：i-len(p)+1。 若字符集已知为小写字母，优先用数组计数，常数更小。 一句话复盘：这题本质是“固定长度窗口下的频次匹配”，关键在窗口预热与增减计数同步。 前缀和 + 哈希类题目（和为 K 的子数组） 日期：2026-03-02 难点类型：题型识别 / 状态转换 常见误判：容易先往滑动窗口上套，但这题数组元素可正可负，窗口和不具备单调性，无法稳定通过“扩窗/缩窗”判断方向。 核心思路： 设 pre[i] 为前 i 个元素前缀和，则区间和满足：sum(l..r) = pre[r] - pre[l-1]。 遍历过程中用哈希表记录前缀和出现次数，查询当前 pre - k 出现了多少次，即有多少个区间以当前位置结尾且和为 k。 本质是用空间换时间，把区间和匹配从 O(n^2) 降到 O(n)。 注意事项： 初始化 count[0] = 1，表示“前缀和为 0 的空前缀”出现过一次。 统计顺序通常是先加答案 ans += count[pre-k]，再更新 count[pre]++，避免把当前前缀和提前用于自身匹配。 这里是“子数组”问题（连续区间），不是子串。 一句话复盘：和为 K 的子数组要先想到前缀和差值，再用哈希表做快速计数。 滑动窗口类题目（滑动窗口最大值） 日期：2026-03-03 难点类型：数据结构选择 / 边界处理 核心思路：用单调结构维护窗口内可能成为最大值的元素，并在窗口滑动时及时移除过期下标。 关键突破：这题本质上要用单调双端队列（deque），不是普通单调栈；因为既要从尾部维护单调性，也要从头部弹出过期元素。 注意事项： 队列里通常存下标而不是值，便于判断是否超出窗口左边界。 入队前从队尾弹出所有小于等于当前值的下标，保证队列单调递减。 若队首下标 <= i-k，说明已离开窗口，需要弹出。 当 i >= k-1 时，队首对应当前窗口最大值。 可用数组模拟双端队列完成上述操作。 一句话复盘：滑动窗口最大值的关键是“单调队列 + 过期下标淘汰”。 数组类题目（合并区间） 日期：2026-03-03 难点类型：排序后处理 / 区间边界维护 核心思路：先按区间左端点排序，再线性扫描合并重叠区间。 关键突破：排序后，后续区间只可能与当前合并段发生关系，处理逻辑会变成单次遍历。 注意事项： Go 中可用 slices.SortFunc 自定义排序： slices.SortFunc(intervals, func(a, b []int) int { return a[0] - b[0] }) 扫描时维护当前区间 [l, r]： 若下一个区间左端点 <= r，则可合并并更新 r = max(r, nextR)。 否则先把当前区间写入答案，再开启新区间。 时间复杂度 O(n log n)（排序主导），空间复杂度取决于结果集与实现方式。 一句话复盘：合并区间的本质是“先排序，再按边界关系合并”。 数组类题目（轮转数组） 日期：2026-03-03 难点类型：下标变换 / 原地操作 核心思路：三次翻转法。先整体翻转，再把前半段和后半段各翻转一次，即可完成右移轮转。 关键步骤： 先做 k %= n，统一轮转步数。 翻转整个数组。 翻转前 k 个元素。 翻转后 n-k 个元素。 注意事项： k 可能大于数组长度，不取模会导致区间错误。 特殊情况如 n == 0 时要提前返回，避免取模异常。 时间复杂度 O(n)，额外空间复杂度 O(1)。 一句话复盘：轮转数组本质是“位置映射”，三次翻转是最稳的原地实现。 数组类题目（除自身以外数组的乘积） 日期：2026-03-03 难点类型：题意约束识别 / 前后缀构造 常见误判：先求整体乘积再除以当前元素，但会被 0 元素和“不能使用除法”的限制卡住。 核心思路：用两段前缀乘积思想。 left[i] 表示 i 左侧所有元素乘积。 right[i] 表示 i 右侧所有元素乘积。 答案为 ans[i] = left[i] * right[i]。 注意事项： 可显式构造两个数组，也可先把左乘积写入 ans，再用一个变量从右往左累乘，做到 O(1) 额外空间（不计输出）。 边界初始化很关键：最左侧的左乘积和最右侧的右乘积都应为 1。 时间复杂度 O(n)。 一句话复盘：这题关键是把“当前元素之外”拆成左半和右半，再做乘积合并。 数组类题目（缺失的第一个正数） 日期：2026-03-03 难点类型：复杂度约束识别 / 解法切换 常见误判：先想到排序，但排序是 O(n log n)，不满足题目要求的 O(n) 时间复杂度。 核心思路：用哈希表记录出现过的正整数，再从 1 开始递增检查第一个不存在的数。 注意事项： 只关心正数，非正数可以直接忽略。 哈希做法时间复杂度 O(n)，空间复杂度 O(n)，属于用空间换时间。 这题还有进阶的原地做法（下标映射/原地哈希）可把额外空间降到 O(1)。 一句话复盘：先看清复杂度约束，再从排序思路切到哈希或原地哈希方案。 矩阵类题目（矩阵置零） 日期：2026-03-03 难点类型：状态标记 / 原地修改时机 核心思路：先遍历矩阵记录哪些行、哪些列需要置零，再二次遍历统一置零。 关键突破：把“发现 0”和“执行置 0”分两阶段，避免在遍历中提前改值污染后续判断。 注意事项： 用 rowZero[m]、colZero[n] 分别标记目标行列。 第二次遍历时，只要 rowZero[i] 或 colZero[j] 为真，就把 matrix[i][j] 设为 0。 该解法时间复杂度 O(m*n)，额外空间复杂度 O(m+n)。 题目若要求常数空间，可进一步用首行首列当标记位优化。 一句话复盘：矩阵置零的核心是“先标记，后落地”，避免边改边判断。 通用注意事项（持续补充） 高频思维误区（持续补充）