笔记
数组与哈希
模式速查表
| 如果问题提到了… | 思考… |
|---|---|
| 重复 / 频率计数 | 哈希表 / Counter |
| “我们是否已经见过？” | 哈希表 / 集合 |
| 范围和 | 预缀和 (1D 或 2D) |
| O(n²) 暴力法 | 哈希 / 预缀和 / 排序 |
| 组队 | 带有键的哈希表 (通常是排序 / 元组) |
| “原地” | 两个指针 / 交换 |
| 最大 / 最小利润 / 分数 | 贪心 / 运行的最小 / 最大 |
| 恒定时间查询 | 预处理 (预缀，哈希表) |
| 子数组 / 窗口 | 滑动窗口 + 哈希表 / 集合 |
| “连续” 值 | 集合 + O(1) 查找 |
如何思考数组和哈希问题
即使问题看起来很复杂，但许多问题都可以简化为 对数组进行一次或两次遍历，加上某种 辅助结构（哈希表、预缀和等）。
你可能会看到很多：
- 对 1D 列表进行单次或两次遍历的解决方案
- 巧妙地使用哈希表 / 集合来避免嵌套循环
- 排序来分组或排序元素
- 简单的构建块在更复杂的程序中重复使用
排序也经常出现，例如：
- 归并排序 – 例如 “排序数组” (LC 912)
- 原地排序 – 例如 “排序颜色” (LC 75)
- 桶 / 计数风格方法 – 例如 “Top K 频繁元素” (LC 347)
核心技术
以下是你掌握数组和哈希的常用工具：
-
预缀和技术
- 构建预缀和 / 乘积或后缀数组，以回答范围查询或避免重复计算。
- 示例：数组形式：除了自身之外 (LC 238) 使用预缀和和后缀乘积而不是除法，在 O(n) 时间和 O(1) 额外空间内（不包括输出）。
-
使用哈希表 / 集合来降低复杂性 当你想要：
- 跟踪计数或频率
- 在平均 O(1) 时间内检查成员
- 避免多次扫描数组
经典问题：
- Contains Duplicate (LC 217) – 使用集合来检测重复项。
- Valid Sudoku (LC 36) – 使用每行 / 每列 / 盒子的哈希集合。
- Group Anagrams (LC 49) – 使用一个签名（排序字符串或字母计数）作为哈希表，将单词映射到列表。
- Longest Consecutive Sequence (LC 128) – 将所有内容放入集合中，然后在“序列开始”时仅开始计数。
-
多数元素模式
- 识别何时某个东西“出现超过 n/2 次”或“出现超过 n/3 次”。
- 基本：Majority Element (LC 169) – 使用 Boyer–Moore 投票算法，在 O(n) 时间和 O(1) 空间内。
- 变体模式也出现在更高级的问题中。
-
二维数组 / 矩阵 + 预缀和
- 将矩阵视为数组的 2D 扩展。
- 预先计算 2D 预缀和，以在 O(1) 时间内回答子矩阵查询，并在 O(m·n) 预处理后。
- 示例：Range Sum Query 2D – Immutable (LC 304)。
-
连续序列
-
任何提到“连续整数”或“序列”的问题，都应该想到 集合 + 邻居。
-
示例：Longest Consecutive Sequence (LC 128):
- 将所有数字插入到集合中
- 对于每个数字，只有在
num - 1不在集合中时才扩展（即，它是序列的开始）。
-