Skip to content

1. 本篇解决什么问题 ​

先读基础知识,完成一次数组扫描。本篇对应学习路线第 02 周:当一个算法不断询问“以前出现过吗”“出现在哪里”“出现了几次”,可以考虑保存已经处理过的信息。

数组仍用于保存有序输入,哈希结构用于辅助查询。是否增加额外空间,应根据题目允许的空间与查询次数决定,不是见到数组就建立哈希表。

需要回答的问题保存的信息工具
是否出现过不重复的值Set
出现在哪里值到下标Map
出现几次值到次数Map

本文按常见哈希实现的平均常数查询成本分析;语言接口本身不承诺每次操作都严格为 O(1)。示例不修改输入;数值练习假定安全整数,涉及加减时中间结果也在安全整数范围内,不处理任意外部输入的类型转换。

2. 重复元素:保存已经见过的值 ​

2.1 从两两比较到一次扫描 ​

朴素方法将每个元素与其后面的元素比较,总计最多 n(n - 1) / 2 次,时间为 O(n²),辅助空间为 O(1)。

优化时,每处理一个值,只需要知道它是否出现在已经处理的前缀里。循环开始前,seen 恰好记录此前出现过的值;检查后再加入当前值。

js
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;因此可以把“试遍所有旧值”改为一次查询。

js
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 代码点遍历。它不按用户可见字素簇分组,也不自动进行大小写或规范化转换。例如视觉相同的组合字符,编码方式不同仍可能判为不同。

js
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. 边界与独立练习 ​

练习必须检查的边界要能解释的问题
重复元素空、单元素、非相邻重复集合在循环前代表哪一段输入?
两数之和无解、相同值、零下标、负数为什么不能先保存当前元素?
字符计数空串、次数不同、大小写、非基本平面字符为什么不能只比较字符集合?

文档示例由以下测试直接读取执行:

sh
node --test tests/algorithm-linear-examples.test.mjs

学习时不要只运行现成测试:自己写一个失败用例、解释原因,再隔几天闭卷重写一道题。变式练习可以选“两个数组是否包含相同元素及次数”,沿用计数思路但重新明确元素类型和相等规则。

下一篇是双指针与滑动窗口。到第 04 周,再学习前缀和如何处理重复的区间求和。

评论

正在加载评论…