哈希表高频题（两数之和/异位词/连续序列） - 面试题

#

★★★

1. 两数之和（LeetCode 1）中用哈希表存“补数→下标”能把 O(n²) 降到 O(n)，先查后存如何避免误用同一元素？

问题

两数之和，说明为何用哈希表存"补数→下标"能把 O(n²) 降到 O(n)，以及先查后存如何避免误用同一元素？

考察点

哈希表存补数→下标
O(n²) → O(n)
先查后存避免重复使用

答案

两数之和：遍历数组，对每个元素 x，查"target-x"是否已在哈希表中；若在则返回下标对，否则把 x 存入哈希表（x→下标）。复杂度从 O(n²)（双重循环）降到 O(n)：哈希表查找平均 O(1)，把"找补数"从线性扫描变为哈希查询。先查后存避免误用同一元素：若先存后查，当 x==target-x（两倍关系）时，当前元素会查到"自己"，误用同一元素；先查后存保证"补数"是之前已存的元素（下标不同），不会把当前元素自身当作补数。故先查后存是关键。

解析

哈希表把"补数查找"从 O(n) 变 O(1)，是空间换时间。先查后存保证补数来自"已遍历的、不同下标的"元素，避免 self-pair 误用。这是"哈希表 + 遍历"的经典题。

示例代码

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int complement = target - nums[i];
        if (map.containsKey(complement)) return new int[]{map.get(complement), i};
        map.put(nums[i], i); // 先查后存
    }
    return new int[]{};
}

#

★★★

2. 字母异位词分组（LeetCode 49）中排序后作 key 与字符计数数组作 key 的取舍，时间复杂度与内存各是多少？

问题

字母异位词分组，说明排序后作 key 与字符计数数组作 key 的取舍，以及时间与内存？

考察点

排序后作 key
字符计数作 key
复杂度与内存

答案

字母异位词分组：把异位词（相同字符不同顺序）分到一组。两种 key：① 排序后作 key：对每个单词排序，排序后的字符串作为 key（异位词排序后相同），加入对应组。时间复杂度 O(n·L log L)（n 为单词数，L 为单词长度），内存 O(nL)。② 字符计数作 key：用字符计数数组（26 位）编码成 key，如 "1#2#3..."，异位词计数相同。时间复杂度 O(n·L)（无需排序），内存 O(nL)。取舍：计数法时间复杂度更低（无排序 log L），但编码 key 需构造字符串；排序法实现简单直观。单词短时差异不大，长单词计数法更优。

解析

异位词的判别是"字符多重集相同"，两种 key 分别用"排序后的规范形"与"计数签名"表示。排序法 O(nL log L)，计数法 O(nL)。选型看单词长度与实现偏好。

示例代码

// 计数作 key
List<List<String>> groupAnagrams(String[] strs) {
    Map<String, List<String>> map = new HashMap<>();
    for (String s : strs) {
        int[] cnt = new int[26];
        for (char c : s.toCharArray()) cnt[c - 'a']++;
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < 26; i++) sb.append(cnt[i]).append('#');
        String key = sb.toString();
        map.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
    }
    return new ArrayList<>(map.values());
}

#

★★★

3. 最长连续序列（LeetCode 128）中为什么先放入哈希集合去重、再只从“序列起点”向两端扩展能保证 O(n)？

问题

最长连续序列，说明为何先放入哈希集合去重、再只从序列起点扩展能保证 O(n)？

考察点

哈希集合去重
只从序列起点扩展
O(n) 保证

答案

最长连续序列：把元素放入哈希集合（去重）。遍历每个元素 x，若 x-1 不在集合中（说明 x 是某连续序列的起点），则从 x 开始向 x+1、x+2... 扩展，直到不在集合中，记录长度。为什么 O(n)：每个元素只被"起点"发起扩展时访问一次，且扩展时每个元素至多被访问一次（作为某序列的一部分）；非起点元素（x-1 在集合中）不发起扩展，直接被跳过。故总访问 O(n)，哈希集合 O(1) 查询。若对每个元素都向两端扩展会 O(n²)，只从起点扩展避免重复。

解析

关键优化是"只从序列起点扩展"：起点是 x-1 不在集合中的元素，这样每个连续序列只被完全遍历一次，总 O(n)。去重集合保证 O(1) 判断。这是"哈希集合 + 起点判定"的经典思路。

示例代码

int longestConsecutive(int[] nums) {
    Set<Integer> set = new HashSet<>();
    for (int x : nums) set.add(x);
    int best = 0;
    for (int x : set) {
        if (!set.contains(x - 1)) { // 序列起点
            int len = 1, cur = x;
            while (set.contains(cur + 1)) { cur++; len++; }
            best = Math.max(best, len);
        }
    }
    return best;
}

#

★★★

4. 前 K 个高频元素（LeetCode 347）中统计频率后如何用大小为 K 的小顶堆或桶排序求解？

问题

前 K 个高频元素，说明统计频率后用大小为 K 的小顶堆或桶排序求解？

考察点

频率统计（哈希表）
小顶堆维护前 K
桶排序（按频率分桶）

答案

前 K 个高频元素：① 用哈希表统计每个元素频率；② 用小顶堆（大小为 K）维护频率最高的 K 个：遍历频率表，若堆未满则入堆，若堆满且当前频率 > 堆顶（最小频率）则替换堆顶。堆顶是第 K 高频，堆内即前 K 大。复杂度 O(n log K)。③ 桶排序：按频率分桶（桶数组下标为频率，桶内存该频率的元素），从高频率桶向下收集直到取满 K 个。复杂度 O(n)。取舍：小顶堆 O(n log K) 且适合"前 K 大"流式；桶排序 O(n) 但需频率最大值（数组长度）作桶数，适合频率范围有限。

解析

频率统计是前置，求前 K 高频用"Top-K"两种工具：小顶堆（O(n log K)）与桶排序（O(n)）。桶排序利用"频率范围 ≤ n"的分桶收集，比堆更快但需额外桶数组。这是"哈希统计 + Top-K"的经典题。

示例代码

// 小顶堆
Map<Integer, Integer> freq = new HashMap<>();
for (int x : nums) freq.merge(x, 1, Integer::sum);
PriorityQueue<Integer> heap = new PriorityQueue<>((a, b) -> freq.get(a) - freq.get(b));
for (int key : freq.keySet()) {
    heap.offer(key);
    if (heap.size() > k) heap.poll(); // 淘汰最小
}
// heap 中即前 K 高频

#

★★★

5. 设计 O(1) 随机集合（380），哈希表存下标与动态数组配合删除时的末尾交换删除技巧

问题

设计 O(1) 随机集合，说明哈希表存下标与动态数组配合删除时的末尾交换删除技巧？

考察点

哈希表存元素→下标
动态数组存元素
末尾交换删除 O(1)

答案

O(1) 随机集合：用动态数组 list 存元素 + 哈希表 map 存元素→下标。insert：若已存在返回 false；否则加入 list 尾，map 存下标。getRandom：随机取 list 的下标。remove：关键技巧——先把待删元素与 list 末尾元素交换，再删除末尾，同时更新 map 中末尾元素的旧下标。这样数组删除是 O(1)（删末尾），避免数组中间删除的 O(n) 移动。步骤：① 查 map 得 idx；② 令 last=list 末尾，把 list[idx]=last，list 删除末尾；③ 更新 map[last]=idx，删除 map[待删元素]。交换删除保证 O(1) 时间。注意处理待删元素就是末尾的情况。

解析

"末尾交换删除"是数组 O(1) 删除的经典技巧：把删中间变成删末尾，配合哈希表更新被交换元素的下标。getRandom 用洗牌数组的随机下标。这是"哈希表 + 数组"的 O(1) 数据结构设计。

示例代码

class RandomizedSet {
    List<Integer> list = new ArrayList<>();
    Map<Integer, Integer> map = new HashMap<>();
    boolean remove(int val) {
        if (!map.containsKey(val)) return false;
        int idx = map.get(val);
        int last = list.get(list.size() - 1);
        list.set(idx, last);            // 末尾元素移到 idx
        map.put(last, idx);             // 更新下标
        list.remove(list.size() - 1);   // 删末尾
        map.remove(val);
        return true;
    }
}

#

★★

6. 有效的字母异位词（LeetCode 242）中字符计数数组 O(n) 判定，扩展到 Unicode 字符集时如何改用哈希表计数？

问题

有效的字母异位词，说明字符计数数组 O(n) 判定，以及扩展到 Unicode 时如何改用哈希表计数？

考察点

字符计数数组 O(n)
Unicode 时用哈希表
计数差异

答案

有效字母异位词：两字符串字符计数组相同。用 int[26] 计数数组：遍历 s 时 +1、t 时 -1，最后检查数组是否全 0（或比较两个数组）。O(n) 时间、O(1) 空间（固定 26）。扩展到 Unicode/任意字符集：字符范围不再限于 26，无法用固定数组，改用哈希表 Map<Character,Integer> 计数：遍历 s 的字符计数 +1、t 的字符计数 -1，最后检查所有计数值为 0。空间 O(字符种类数)。迁移点：计数容器从"固定数组"换成"哈希表"以支持可变/大字符集。

解析

核心是"字符多重集相等"的判定。字母场景用固定数组 O(1) 空间，Unicode 场景用哈希表（O(字符种类)）。理解"计数容器随字符集伸缩"是迁移的关键。

示例代码

// Unicode 用哈希表
boolean isAnagram(String s, String t) {
    if (s.length() != t.length()) return false;
    Map<Character, Integer> map = new HashMap<>();
    for (char c : s.toCharArray()) map.merge(c, 1, Integer::sum);
    for (char c : t.toCharArray()) {
        int v = map.getOrDefault(c, 0);
        if (v == 0) return false;
        map.put(c, v - 1);
    }
    return true;
}

#

★★

7. 四数相加 II（LeetCode 454）中如何把四个数组拆成“两两求和+哈希计数”从而 O(n²)？

问题

四数相加 II，说明如何把四个数组拆成"两两求和+哈希计数"从而 O(n²)？

考察点

拆成两两求和
哈希表计数
O(n²) 复杂度

答案

四数相加 II：四个数组 A、B、C、D，求 i+j+k+l=0 的四元组数。拆成两两求和：先遍历 A、B 的所有组合，把 a+b 存哈希表（值→出现次数）；再遍历 C、D 的所有组合，查 -(c+d) 在哈希表中的次数，累加。复杂度 O(n²)（两次 O(n²) 遍历，每次哈希 O(1)）。相比四重循环 O(n⁴)，拆半后 O(n²)。关键是"两两分组 + 哈希计数"，把 4 元组合问题降为 2 元组合 + 哈希查询。

解析

拆半技巧：把 4 个数组拆成 2+2，用哈希表存"前两组的和"计数，再对"后两组的和"查补数。这是"分治 + 哈希"把 O(n⁴) 变 O(n²) 的经典。与两数之和同构（每个元素变为"一对的和"）。

示例代码

int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
    Map<Integer, Integer> map = new HashMap<>();
    for (int a : A) for (int b : B) map.merge(a + b, 1, Integer::sum);
    int count = 0;
    for (int c : C) for (int d : D) count += map.getOrDefault(-(c + d), 0);
    return count;
}

#

★★

8. 同构字符串（LeetCode 205）中需要双向映射，只用单向映射会漏判什么？

问题

同构字符串，说明为何需要双向映射，以及只用单向映射会漏判什么？

考察点

同构定义（一一对应）
双向映射
单向映射漏判

答案

同构字符串：s 与 t 的字符存在一一对应（一个 s 字符映射到 t 中固定字符，且反之亦然）。需要双向映射：① s→t 映射（s 的每个字符映射到 t 的对应字符）；② t→s 映射（t 的每个字符映射到 s 的对应字符）。只用单向映射会漏判的错误：如 s="ab", t="aa"——若只检查 s→t，a→a、b→a（b 映射到 a 第一次出现），但 t 的字符 a 被两个不同 s 字符映射，违反"一一对应"（t 中 a 应对应仅一个 s 字符）。双向映射能检测这种"多对一"问题：t→s 映射中 a 应只映射到一个 s 字符，但 s 中 a、b 都映射到 t 的 a，导致 t→s 冲突。故需双向映射保证唯一的互逆关系。

解析

同构要求"一一对应（双射）"，单向映射只保证"每个 s 字符唯一映射"，无法保证"每个 t 字符唯一被映射"（多对一漏判）。双向映射同时检查 s→t 与 t→s，能捕获"两个 s 字符映射到同一 t 字符"的违例。

示例代码

boolean isIsomorphic(String s, String t) {
    Map<Character, Character> m1 = new HashMap<>(), m2 = new HashMap<>();
    for (int i = 0; i < s.length(); i++) {
        char cs = s.charAt(i), ct = t.charAt(i);
        if (m1.containsKey(cs) && m1.get(cs) != ct) return false;
        if (m2.containsKey(ct) && m2.get(ct) != cs) return false;
        m1.put(cs, ct); m2.put(ct, cs); // 双向
    }
    return true;
}

#

★★

9. 快乐数（LeetCode 202）中如何用哈希集合检测循环，与 Floyd 判圈的取舍？

问题

快乐数，说明如何用哈希集合检测循环，以及与 Floyd 判圈的取舍？

考察点

快乐数迭代
哈希集合检测循环
Floyd 判圈

答案

快乐数：反复把数替换为各位数字平方和，若最终到 1 则快乐，否则进入循环。哈希集合检测循环：迭代时把每个出现过的数放入集合，若某数已出现过（说明进入循环）则不是快乐数，返回 false；若到 1 则 true。空间 O(循环长度)。Floyd 判圈：用快慢指针检测循环，快指针每次迭代两次、慢指针一次，若相遇则进入循环（非快乐数），若到 1 则快乐。Floyd 空间 O(1)，适合"无法用集合或需省空间"的场景。取舍：哈希集合简单直观，Floyd 省空间。对快乐数，迭代值有界（最大位数平方和），哈希集合足够。

解析

快乐数是"检测迭代是否进入循环"的经典题。哈希集合记录出现过的数（空间 O(循环)），Floyd 判圈用快慢指针（空间 O(1)）。两者都能检测循环，选型看空间约束。

示例代码

// 哈希集合
Set<Integer> seen = new HashSet<>();
while (n != 1 && seen.add(n)) n = sumSquares(n);
return n == 1;
// Floyd 判圈
int slow = n, fast = sumSquares(n);
while (fast != 1 && slow != fast) { slow = sumSquares(slow); fast = sumSquares(sumSquares(fast)); }
return fast == 1;

#

★★

10. 存在重复元素 II（LeetCode 219）中哈希表记录最近一次下标与滑动窗口集合两种解法？

问题

存在重复元素 II，说明哈希表记录最近一次下标与滑动窗口集合两种解法？

考察点

哈希表记录最近下标
滑动窗口集合
复杂度

答案

存在重复元素 II：判断是否存在 i、j 使 nums[i]==nums[j] 且 |i-j|≤k。解法一：哈希表记录每个元素最近一次出现的下标，遍历时若元素已存在且当前下标 - 最近下标 ≤k 则返回 true，否则更新最近下标。O(n) 时间、O(n) 空间。解法二：滑动窗口集合——维护一个大小为 k 的集合（窗口内元素），遍历时若当前元素已在集合中则返回 true，否则加入并移除窗口外（下标 i-k）的元素。集合大小 ≤k，O(n) 时间、O(k) 空间。两者都 O(n)，哈希表存所有下标、滑动窗口存窗口内 k 个元素（空间更小）。

解析

哈希表法"记录最近下标"直接判断距离；滑动窗口法"维护窗口内 k 个元素"判断重复。两者都 O(n) 时间，区别在空间（哈希表 O(n) vs 窗口 O(k)）。滑动窗口利用"距离≤k"限制窗口大小。

示例代码

// 滑动窗口集合
Set<Integer> set = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
    if (set.contains(nums[i])) return true;
    set.add(nums[i]);
    if (set.size() > k) set.remove(nums[i - k]); // 移除窗口外
}
return false;

#

★★

11. 猜数字游戏（LeetCode 299）中如何一遍扫描统计 bulls，并用计数数组计算 cows？

问题

猜数字游戏，说明如何一遍扫描统计 bulls，并用计数数组计算 cows？

考察点

bulls：位置与值都匹配
cows：值匹配位置不同
计数数组

答案

猜数字游戏：secret 与 guess 同长数字。bulls：位置与值都相同的个数（猜对且位置对）。cows：值对但位置错的个数（去掉 bulls 后的公共值频次）。一遍扫描统计 bulls：同时遍历 secret 与 guess，若相同则 bulls++，否则分别统计 secret 的每个数字频次与 guess 的每个数字频次。计算 cows：对每个数字，cows += min(secret 频次, guess 频次)（两者都出现的最小公共频次），最后 cows 减去已算进 bulls 的部分（bulls 已位置匹配，不算 cows）。或用一维计数数组：对非 bull 位置，secret 数字 +1、guess 数字 -1，统计时累计对顶的频次。最终 "xAyB"。

解析

一遍扫描：bulls 直接比较，非 bull 的 secret/guess 分别计数。cows 用"两个计数数组取 min 的公共频次"得到（值相同但位置不同的对数）。bulls 位置匹配不参与 cows。这是"计数数组 + 双频次"的题。

示例代码

String getHint(String secret, String guess) {
    int bulls = 0, cows = 0;
    int[] s = new int[10], g = new int[10];
    for (int i = 0; i < secret.length(); i++) {
        if (secret.charAt(i) == guess.charAt(i)) bulls++;
        else { s[secret.charAt(i) - '0']++; g[guess.charAt(i) - '0']++; }
    }
    for (int i = 0; i < 10; i++) cows += Math.min(s[i], g[i]); // 公共频次
    return bulls + "A" + cows + "B";
}

#

★★

12. 找出所有消失的数字（LeetCode 448）中为什么能用“值作下标取负”的原地标记法，与哈希集合的对比？

问题

找出所有消失的数字，说明为何能用"值作下标取负"的原地标记法，以及与哈希集合的对比？

考察点

值作下标取负标记
原地 O(1) 空间
与哈希集合对比

答案

找出所有消失的数字：nums 长度 n，元素范围 [1,n]，找出 [1,n] 中未出现的数。原地标记法：遍历每个元素 x，用其绝对值 index=|x|-1 作为下标，把 nums[index] 取负（标记"该值出现过"）。第二次遍历，若 nums[i] 仍为正，说明值 i+1 未出现，加入结果。为什么可行：元素范围 [1,n] 与数组长度 n 对应，值可作下标；取负不改值（后续用绝对值），避免破坏。原地标记 O(1) 空间。与哈希集合对比：哈希集合需 O(n) 空间存已出现元素，原地标记用数组本身存"是否出现"标记（负号），省空间。这是"值作下标 + 符号标记"的经典技巧。

解析

核心是"值域 [1,n] 与下标 [0,n-1] 的映射 + 符号标记"。用负号标记"该值出现过"，第二次扫描正数即未出现。空间 O(1) 优于哈希集合 O(n)。这是"原地标记"的哈希替代。

示例代码

List<Integer> findDisappearedNumbers(int[] nums) {
    for (int x : nums) {
        int idx = Math.abs(x) - 1;
        if (nums[idx] > 0) nums[idx] = -nums[idx]; // 标记
    }
    List<Integer> res = new ArrayList<>();
    for (int i = 0; i < nums.length; i++) if (nums[i] > 0) res.add(i + 1);
    return res;
}

#

★★

13. 寻找重复数（LeetCode 287）中如何用“值作下标”建图 + Floyd 判圈，与哈希/排序解法的取舍？

问题

寻找重复数，说明如何用"值作下标"建图 + Floyd 判圈，以及与哈希/排序解法的取舍？

考察点

值作下标建图
Floyd 判圈找重复
与哈希/排序取舍

答案

寻找重复数：nums 长度 n+1，元素范围 [1,n]，存在一个重复数。不修改数组、O(1) 空间解法：把"值作下标"建图——把 nums[i] 看作从 i 指向 nums[i] 的边，因元素范围 [1,n] 且存在重复，该图必有环（某节点被多次指向），重复数即环的入口。用 Floyd 判圈（快慢指针）找环：slow=nums[0], fast=nums[nums[0]]，快慢相遇后，把 slow 重置为 0，两指针同速走，相遇点即环入口（重复数）。O(n) 时间、O(1) 空间。与哈希/排序取舍：哈希集合 O(n) 空间简单，排序 O(n log n) 时间（可 O(1) 空间但修改数组），Floyd 判圈 O(n) 时间 + O(1) 空间且不修改数组，是最优解（满足"不修改数组、O(1) 空间"约束）。

解析

关键是把"寻找重复数"转化为"多对一映射构成的环 + 找环入口"。值作下标建图后，重复数对应环的入口，用 Floyd 判圈 O(1) 空间。这是"哈希（map）与判圈"的巧妙结合，也是"不修改数组"约束下的最优解。

示例代码

int findDuplicate(int[] nums) {
    int slow = nums[0], fast = nums[nums[0]];
    while (slow != fast) { slow = nums[slow]; fast = nums[nums[fast]]; }
    slow = 0;
    while (slow != fast) { slow = nums[slow]; fast = nums[fast]; }
    return slow; // 环入口 = 重复数
}

#

★★

14. 赎金信（LeetCode 383）中字符计数判定 magazine 能否构成 ransomNote 的边界条件？

问题

赎金信，说明字符计数判定 magazine 能否构成 ransomNote 的边界条件？

考察点

字符计数
ransomNote 字符数 ≤ magazine
边界条件

答案

赎金信：判断 ransomNote 能否由 magazine 的字符构成（magazine 每个字符最多用一次）。字符计数：统计 magazine 中每个字符出现次数，然后遍历 ransomNote，若某字符计数为 0 则 false（不够），否则减 1。边界条件：① ransomNote 长度大于 magazine 长度时必 false（字符不够）；② magazine 中某字符计数不足时 false；③ 空串：空 ransomNote 总是 true（无需字符）。核心是"magazine 的字符频次必须 ≥ ransomNote 的频次"。用固定数组（26 字母）或哈希表（Unicode）计数。

解析

这是"多重集包含"判定：magazine 的字符多重集必须包含 ransomNote 的字符多重集。计数 magazine 后逐字符扣减，不足则失败。边界是长度与频次不足。

示例代码

boolean canConstruct(String ransomNote, String magazine) {
    int[] cnt = new int[26];
    for (char c : magazine.toCharArray()) cnt[c - 'a']++;
    for (char c : ransomNote.toCharArray())
        if (--cnt[c - 'a'] < 0) return false; // 不够
    return true;
}

#

★★

15. 单词规律（LeetCode 290）中如何用“模式字符↔单词”双向映射保证一一对应？

问题

单词规律，说明如何用"模式字符↔单词"双向映射保证一一对应？

考察点

模式字符→单词映射
单词→模式字符映射
双向保证一一对应

答案

单词规律：判断 pattern 与 words 是否一一对应（相同模式字符对应相同单词，且不同字符对应不同单词）。双向映射：① 模式字符→单词：pattern 的每个字符映射到 words 的对应单词；② 单词→模式字符：每个单词映射到对应模式字符。遍历时检查两者都一致，否则 false。为什么需要双向：单向映射只能保证"相同字符对应相同单词"，无法保证"不同字符对应不同单词"（如 pattern="ab", words=["dog","dog"]，单向 a→dog、b→dog 通过，但 a、b 应对应不同单词）。双向映射检测"多对一/一对多"的冲突，保证一一对应。

解析

与同构字符串同理，单词规律要求"一一对应（双射）"。双向映射（pattern→word 与 word→pattern）同时检查两个方向，捕获"不同字符映射同一单词"或"同一字符映射不同单词"的违例。

示例代码

boolean wordPattern(String pattern, String s) {
    String[] words = s.split(" ");
    if (pattern.length() != words.length) return false;
    Map<Character, String> m1 = new HashMap<>();
    Map<String, Character> m2 = new HashMap<>();
    for (int i = 0; i < pattern.length(); i++) {
        char c = pattern.charAt(i); String w = words[i];
        if (m1.containsKey(c) && !m1.get(c).equals(w)) return false;
        if (m2.containsKey(w) && m2.get(w) != c) return false;
        m1.put(c, w); m2.put(w, c);
    }
    return true;
}

#

★★

16. 重复 DNA 序列（187）中如何用滚动哈希加集合去重找出长度 10 的重复子串，与直接子串比较的复杂度对比

问题

重复 DNA 序列，说明如何用滚动哈希加集合去重找出长度 10 的重复子串，与直接子串比较的复杂度对比？

考察点

长度 10 的子串
滚动哈希（Rabin-Karp）
与直接子串比较对比

答案

重复 DNA 序列：找出所有长度为 10 且在 s 中出现多次的子串。直接子串比较：用集合存所有长度 10 的子串（substring O(10) 每次），若重复加入结果，O(n·10) 时间、O(n·10) 空间。滚动哈希（Rabin-Karp）：把每个字符编码（A/C/G/T），用滚动哈希 O(1) 计算每个长度 10 窗口的哈希，存集合去重。O(n) 时间、O(n) 空间。复杂度对比：直接子串每次 substring 开销 O(10)（可视为常数），滚动哈希用 O(1) 滑动窗口哈希，总 O(n) 与 O(n·10) 在常数上有差异；对长序列滚动哈希更优。滚动哈希要处理哈希碰撞（用去重 + 字符串校验）。

解析

滚动哈希把"滑动窗口子串"的匹配从 O(L) 降到 O(1)（用前一个窗口哈希递推），是 Rabin-Karp 的思想。对长度 10 的固定窗口，直接子串的 substring 也接近常数，但滚动哈希理论上更优。集合去重保证"重复出现"。

示例代码

List<String> findRepeatedDnaSequences(String s) {
    Set<String> seen = new HashSet<>(), res = new HashSet<>();
    for (int i = 0; i + 10 <= s.length(); i++) {
        String sub = s.substring(i, i + 10);
        if (!seen.add(sub)) res.add(sub); // 已出现则重复
    }
    return new ArrayList<>(res);
}

#

★

17. 砖墙（LeetCode 554）中统计“各边缘位置出现次数”能求最少穿墙数，边缘如何用前缀和枚举？

问题

砖墙，说明为何统计"各边缘位置出现次数"能求最少穿墙数，以及边缘如何用前缀和枚举？

考察点

穿墙数 = 总行数 - 边缘最大重合
前缀和统计边缘
最少穿墙

答案

砖墙：穿过最少的砖，即选择"边缘重合最多的位置"（竖线经过的位置上，砖缝边缘越多，越少穿砖）。穿墙数 = 总行数 - 该位置重合的边缘数。统计各边缘位置出现次数：对每行砖墙，用前缀和累加砖宽，得到每个边缘位置（行内砖缝），用哈希表统计每个位置被多少行"共享"（即边缘在此位置）。取出现次数最多的位置，最少穿墙数 = 总行数 - 最大出现次数。注意排除最后位置（墙的最右边缘，穿墙数=0 无意义）。O(n) 遍历所有砖。

解析

关键洞察：竖线经过某位置时，若该位置是某行的砖缝边缘，则不穿该行砖；否则穿 1 块。故"穿最小砖"= 找"边缘重合最多"的竖线。前缀和枚举每行边缘，哈希表统计边缘出现次数。这是"映射到位置 + 计数"的题。

示例代码

int leastBricks(List<List<Integer>> wall) {
    Map<Integer, Integer> map = new HashMap<>();
    for (List<Integer> row : wall) {
        int sum = 0;
        for (int i = 0; i < row.size() - 1; i++) { // 排除最右
            sum += row.get(i);
            map.merge(sum, 1, Integer::sum);
        }
    }
    int max = 0;
    for (int v : map.values()) max = Math.max(max, v);
    return wall.size() - max;
}

#

★

18. 自定义字符串排序（LeetCode 791）中如何用计数排序按指定顺序重排字符，与 Comparator 排序的差异？

问题

自定义字符串排序，说明如何用计数排序按指定顺序重排字符，与 Comparator 排序的差异？

考察点

计数排序按指定顺序
稳定重排
与 Comparator 差异

答案

自定义字符串排序：按 order 中字符的先后顺序重排 s 中的字符，order 中未出现的字符可放任意位置（一般放末尾，保持原序）。计数排序法：① 统计 s 中每个字符出现次数；② 按 order 的顺序遍历，把每个字符按次数输出到结果；③ 最后把 order 中未出现的字符（按 s 原序）附加。复杂度 O(n) 时间、O(26) 空间。与 Comparator 排序差异：Comparator 排序用自定义比较器（字符按 order 中的索引比较），O(n log n) 时间，且需额外处理未出现字符的排序；计数排序是"按 order 顺序输出 + 附加剩余"，O(n) 线性、更简单，且天然稳定（未出现字符保持原序）。计数排序适合"字母表固定"的场景。

解析

计数排序利用"字符集固定（26）"与"order 是排列"，按 order 顺序输出即可，避免排序的 O(n log n)。Comparator 排序是通用但慢。计数排序的关键是"先计数，再按指定顺序输出"。

示例代码

String customSortString(String order, String s) {
    int[] cnt = new int[26];
    for (char c : s.toCharArray()) cnt[c - 'a']++;
    StringBuilder sb = new StringBuilder();
    for (char c : order.toCharArray()) while (cnt[c - 'a']-- > 0) sb.append(c);
    for (char c : s.toCharArray()) if (cnt[c - 'a'] > 0) sb.append(c); // 未出现字符
    return sb.toString();
}

#

★

19. 存在重复元素 III（220）中按值宽度分桶如何把窗口内查找降到 O(1)，桶大小与溢出处理

问题

存在重复元素 III，说明按值宽度分桶如何把窗口内查找降到 O(1)，以及桶大小与溢出处理？

考察点

值分桶（按值宽度）
桶内 O(1) 查找
桶大小与溢出

答案

存在重复元素 III：判断是否存在 i、j 使 |nums[i]-nums[j]|≤t 且 |i-j|≤k。按值分桶：把元素按值大小分桶，桶大小 = t+1（每个桶内元素差 ≤t）。对每个元素 x，其桶 id = x/(t+1)（对负数调整）。判断：① 若 x 所在桶已有元素，则差 ≤t 直接命中；② 检查相邻桶（id±1），若相邻桶元素与 x 差 ≤t 也命中。用哈希表存"桶 id→元素值"（每桶只需一个元素，若有多个则必命中）。窗口裁剪：移除窗口外（i-k）元素的桶。桶大小 t+1 保证桶内差 ≤t，桶 id 用 (x - min)/(t+1) 或对负数用 floorDiv 处理。复杂度 O(n)（每元素 O(1) 桶查找）。溢出：用 long 存 x 与差值避免 t+1 或负值溢出。

解析

分桶把"窗口内找差 ≤t 的元素"变为 O(1) 桶查找：桶内必满足，相邻桶需检查。桶大小 t+1、负数用 floorDiv、long 防溢出是细节。这是"值分桶 + 滑动窗口"的经典题。

示例代码

boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
    Map<Long, Long> buckets = new HashMap<>();
    long w = (long) t + 1;
    for (int i = 0; i < nums.length; i++) {
        long id = Math.floorDiv((long) nums[i], w); // 桶 id
        if (buckets.containsKey(id)) return true;
        if (buckets.containsKey(id - 1) && Math.abs(nums[i] - buckets.get(id - 1)) <= t) return true;
        if (buckets.containsKey(id + 1) && Math.abs(nums[i] - buckets.get(id + 1)) <= t) return true;
        buckets.put(id, (long) nums[i]);
        if (i >= k) buckets.remove(Math.floorDiv((long) nums[i - k], w)); // 移除窗口外
    }
    return false;
}