Kevin's Blog

2025年10月12日

01 Array & Hash

LC

1. Contains Duplicate

题目：给一个整数数组，判断是否存在重复元素。

思路：遍历一遍，用 HashSet 记录见过的数，出现重复立刻返回 True。

要点：

  • 时间 O(n)，空间 O(n)。
  • 备选方案：排序后相邻比较，O(n log n) 时间但 O(1) 额外空间（如果允许改原数组）。

2. Valid Anagram

题目：给两个字符串 s 和 t，判断 t 是否是 s 的字母异位词（字符种类和数量完全相同，顺序可以不同）。

思路：统计两个字符串的字符频次，比较是否完全一致。

要点：

  • 如果限定是小写英文字母：用长度 26 的数组做计数，比 HashMap 快且省去哈希开销。
  • 反直觉点：如果字符集不确定（比如 Unicode），26 长度数组会出错，必须退回 HashMap。
  • 备选解法：把两个字符串都排序后比较是否相等，O(n log n)，代码更短但复杂度更差。
  • 长度不等可以直接提前返回 False，是个容易漏掉的剪枝。

3. Two Sum

题目：给一个数组和目标值 target，找出数组中两个数相加等于 target 的下标（假设有且仅有一个解，同一元素不能用两次）。

思路：一次遍历，用 HashMap 存 值 -> 下标。对每个数，先查询 target - num 是否已经在表里，再把当前数存入表中。

要点：

  • 顺序很重要：一定是"先查后存"，否则会把自己算作另一半（比如 target 是当前数的两倍时会误判自己和自己配对）。
  • 这是"一遍哈希"（one-pass hash）的模板题，后面很多题（3Sum 优化、子数组和等于K）都是这个思路的变体：边遍历边维护"互补关系"的哈希表。
  • 返回的是下标而不是值，容易写着写着返回错。

4. Group Anagrams

题目：给一个字符串数组，把所有互为字母异位词的字符串分到同一组。

思路：把每个字符串映射到一个"归一化的key"，key 相同的分到一组。

要点：

  • 朴素做法：对每个字符串排序作为 key，O(n·k log k)，k 是字符串平均长度。最容易想到但不是最优。
  • 进阶技巧：用长度为 26 的字符计数数组（转成 tuple 或字符串后当 key）代替排序，把每个字符串的处理复杂度从 O(k log k) 降到 O(k)，总复杂度 O(n·k)。
  • 反直觉点：计数数组本身不能直接当 HashMap 的 key（大多数语言数组不可哈希），需要转成字符串（如 "1#0#0#2..."）或元组才能用作 key。

5. Top K Frequent Elements

题目：给一个数组，返回出现频率前 k 高的元素。

思路：先统计频次，再找出频次最高的 k 个元素。

要点：

  • 常规解法：堆（heap），维护大小为 k 的小顶堆，O(n log k)。
  • 进阶 O(n) 解法——桶排序（Bucket Sort）：
    • 关键洞察：一个数组里，元素的出现频次上限就是数组长度 n。
    • 建一个大小为 n+1 的桶数组，bucket[freq] 存放"出现了 freq 次的所有元素"。
    • 统计完频次后，从 bucket[n] 往 bucket[0] 倒序遍历，收集元素直到凑够 k 个。
    • 整体做到严格 O(n)，避免了堆的 log 因子。
  • 反直觉点：频次的取值范围表面看是"任意大"，但其实被 n 天然限制住了——"值域被 n 限制 → 可以用计数/桶"是通用技巧，其他一些排序变体题也会用到。

6. Encode and Decode Strings

题目：设计一个算法，把一个字符串列表编码成一个字符串，再能无损解码回原来的列表。

思路：

  • 不能简单用逗号或某个分隔符拼接（如 "apple,banana"），因为原字符串里可能本身就包含这个分隔符，导致解码时切分错误。
  • 正确做法：长度前缀编码（Length-Prefix Encoding）。
    • 编码格式："长度#字符串内容"，比如 "5#hello3#cat"。
    • 解码时：先读到 # 之前的数字，知道接下来要读多少个字符，直接按长度切片，不管内容里有什么符号都不会出错。
  • 口诀：用长度做分隔，而不是用符号做分隔。

7. Product of Array Except Self

题目：给一个数组，返回一个新数组，新数组的第 i 个位置是原数组除了 nums[i] 之外所有元素的乘积。要求不能使用除法，且尽量做到 O(1) 额外空间（不算输出数组）。

思路：对每个位置 i，结果是"i 左边所有数的乘积" × "i 右边所有数的乘积"。

要点：

  • 两遍扫描法：
    1. 第一遍从左到右，result[i] = i 左边所有元素的乘积（不包括自己）。
    2. 第二遍从右到左，用一个变量 postfix 累乘右边的元素，同时 result[i] *= postfix。
  • 空间优化的关键：结果数组本身在第一步就用来存"前缀积"，第二步直接原地乘上"后缀积"，因此除了输出数组外只需要一个 O(1) 的变量（postfix）。
  • 反直觉点：很多人第一反应是开两个数组（prefix 数组 + postfix 数组）分别存，这样是对的但不是最优空间；"复用输出数组"这一步是这题的加分项。

8. Valid Sudoku

题目：判断一个 9×9 的数独局面（部分格子已填数字，部分是空格 .）是否合法，即每行、每列、每个 3×3 宫格内没有重复数字。不要求真的解出数独。

思路：用三组哈希结构：rows[9]、cols[9]、boxes[9]，每个都是一个 Set，一次遍历同时检查三种约束。

要点：

  • 需要记的公式：某个格子 (r, c) 属于哪个 3×3 宫格，用 box_index = (r // 3) * 3 + (c // 3) 计算。
  • 一次遍历（81 格）同时判三种重复，属于"一次遍历 + 多组哈希表"模式（跟 Two Sum 的哈希思路同一类）。
  • 容易和"解数独"的回溯题搞混，注意这题只是验证合法性。

9. Longest Consecutive Sequence

题目：给一个未排序的整数数组，找出最长连续整数序列的长度（序列不要求在原数组中连续出现，只要求数值连续，如 [100,4,200,1,3,2] 中最长是 [1,2,3,4]，长度 4）。要求时间复杂度 O(n)。

思路：

  • 朴素做法：先排序，再遍历找连续段，O(n log n)，能过但不是最优。
  • 进阶 O(n) 解法：
    1. 把所有数放进一个 HashSet（去重 + O(1) 查找）。
    2. 遍历这个 set，只有当 num - 1 不在 set 里时，才把 num 当作一个"序列起点"开始往后数（num+1, num+2, ...）看能数多远。
    3. 其他情况直接跳过。
  • 反直觉点：很多人会想"对每个数都往后数一遍"，这样看似正确但会导致同一个连续段被重复遍历很多次，退化成 O(n²)。只从"序列起点"（左边挨着的数不存在）开始扩展，才能保证每个数只被访问常数次，整体是 O(n)。
  • 口诀：看左边有没有，没有才往右数。

📌 跨题目的通用套路总结

套路 出现在哪些题
一遍哈希，边查边存（顺序敏感） Two Sum
用值域受限的性质做"桶"代替堆/排序 Top K Frequent Elements
用计数数组/元组代替排序作为归一化 key Group Anagrams, Valid Anagram
前缀 + 后缀两次扫描，复用输出数组省空间 Product of Array Except Self
长度前缀而非分隔符做序列化 Encode and Decode Strings
只从"起点"开始扩展避免重复计算 Longest Consecutive Sequence
多组哈希表同时做多维度判重 Valid Sudoku