1. 本篇解决什么问题
先读基础知识,完成一次数组扫描。本篇对应学习路线第 02 周:当一个算法不断询问“以前出现过吗”“出现在哪里”“出现了几次”,可以考虑保存已经处理过的信息。
数组仍用于保存有序输入,哈希结构用于辅助查询。是否增加额外空间,应根据题目允许的空间与查询次数决定,不是见到数组就建立哈希表。
| 需要回答的问题 | 保存的信息 | 工具 |
|---|---|---|
| 是否出现过 | 不重复的值 | Set |
| 出现在哪里 | 值到下标 | Map |
| 出现几次 | 值到次数 | Map |
本文按常见哈希实现的平均常数查询成本分析;语言接口本身不承诺每次操作都严格为 O(1)。示例不修改输入;数值练习假定安全整数,涉及加减时中间结果也在安全整数范围内,不处理任意外部输入的类型转换。
2. 重复元素:保存已经见过的值
2.1 从两两比较到一次扫描
朴素方法将每个元素与其后面的元素比较,总计最多 n(n - 1) / 2 次,时间为 O(n²),辅助空间为 O(1)。
优化时,每处理一个值,只需要知道它是否出现在已经处理的前缀里。循环开始前,seen 恰好记录此前出现过的值;检查后再加入当前值。
function containsDuplicate(nums) {
const seen = new Set();
for (const value of nums) {
if (seen.has(value)) return true;
seen.add(value);
}
return false;
}空数组和单元素数组返回 false。例如 [2, 1, 2]:第一次见到 2 时保存它,第三次读取时集合中已经存在 2,返回 true。
平均时间为 O(n),最坏情况下需要保存所有不同值,辅助空间为 O(n)。空间更紧张时可以考虑排序后检查相邻值,但排序有额外时间成本,原地排序还会改变输入。
2.2 先练一个小变式
关闭代码后改为“返回第一次遇到的重复值,没有则返回 null”。再说明为什么仅用一个记录上一个值的变量,对未排序数组不够用。
3. 两数之和:保存值对应的下标
3.1 契约与推导
给定 nums 和 target,返回一对不同下标 [j, i],使对应值的和等于目标。无解返回 [],有多解时返回任意一对,不重复使用同一元素。
朴素方法枚举两两组合,时间为 O(n²)。当当前值为 value 时,要查找的另一个值已经确定为 target - value;因此可以把“试遍所有旧值”改为一次查询。
function twoSum(nums, target) {
const indexByValue = new Map();
for (let i = 0; i < nums.length; i++) {
const complement = target - nums[i];
if (indexByValue.has(complement)) {
return [indexByValue.get(complement), i];
}
indexByValue.set(nums[i], i);
}
return [];
}处理下标 i 之前,表中只保存下标小于 i 的元素,所以返回的两个下标不同。相同值后续覆盖旧下标也不影响“返回任意一对”的契约;若要返回全部配对或最早的一对,保存策略需要重新设计。
平均时间为 O(n),辅助空间为 O(n)。
3.2 为什么先查再存
[3],目标6:没有答案。若先存当前下标再查询,就可能把同一个元素使用两次。[3, 3],目标6:第二个元素能找到第一个,答案是[0, 1]。[2, 7],目标9:另一个值的下标为0,不能使用if (map.get(...))判断存在性;零会被当成假值。应使用has。
手推时写出每一步的当前值、补数和表内容,而不是只记住一段循环。
4. 字符计数:保存出现次数
4.1 从排序比较到计数抵消
两个字符串是否由相同字符、相同次数组成?排序后比较是可行的朴素方向,但会引入排序和复制成本。另一种方法是统计第一个字符串,再用第二个逐个抵消。
本例区分大小写,空格和标点也计入字符;用 for...of 按 Unicode 代码点遍历。它不按用户可见字素簇分组,也不自动进行大小写或规范化转换。例如视觉相同的组合字符,编码方式不同仍可能判为不同。
function isAnagram(a, b) {
const counts = new Map();
for (const char of a) {
counts.set(char, (counts.get(char) ?? 0) + 1);
}
for (const char of b) {
if (!counts.has(char)) return false;
const remaining = counts.get(char) - 1;
if (remaining === 0) counts.delete(char);
else counts.set(char, remaining);
}
return counts.size === 0;
}处理第二个字符串时,表中保存第一个字符串还没有被抵消的次数。不存在的字符或超出的次数立即失败;遍历结束仍有剩余,也不相同。两个空字符串返回 true。
设代码点数量分别为 m 和 n,平均时间为 O(m + n),辅助空间为 O(k),k 是第一个字符串中的不同代码点数量。只有明确限定为小写英文字母时,才适合把表替换为固定长度的计数数组。
5. 边界与独立练习
| 练习 | 必须检查的边界 | 要能解释的问题 |
|---|---|---|
| 重复元素 | 空、单元素、非相邻重复 | 集合在循环前代表哪一段输入? |
| 两数之和 | 无解、相同值、零下标、负数 | 为什么不能先保存当前元素? |
| 字符计数 | 空串、次数不同、大小写、非基本平面字符 | 为什么不能只比较字符集合? |
文档示例由以下测试直接读取执行:
node --test tests/algorithm-linear-examples.test.mjs学习时不要只运行现成测试:自己写一个失败用例、解释原因,再隔几天闭卷重写一道题。变式练习可以选“两个数组是否包含相同元素及次数”,沿用计数思路但重新明确元素类型和相等规则。
评论
正在加载评论…