数组与哈希：最高频的起手式

这一课你将能做到

1. 判断什么情况下该上 HashMap / HashSet，并写出「边走边查」的标准结构
2. 用计数数组和排序两种方式判断字母异位词，并把异位词分组
3. 说出数组题的四类常见问法（配对、频次、去重、前缀和）及对应套路

为什么要学

数组是所有数据结构的地基：内存连续、按下标 O(1) 随机访问。LeetCode 里大约三分之一的题从数组出发，后端业务里查一批用户 ID、统计接口调用次数、去重一批订单号，也都是同一类动作。

但数组有个短板：按下标找东西快，按「值」找东西慢（要遍历）。哈希表（HashMap、HashSet）正好补上——平均 O(1) 完成查找和插入。数组提供遍历，哈希提供瞬间查找，两者一组合，大量 O(n²) 的暴力解就能降到 O(n)。这是性价比最高的一个模式，也是本课程的第一道实战关卡。

先建立图像

哈希表的本质是一个「字典」：给一个 key，立刻取到 value。

普通数组查找：nums 里有没有 7？  → 从头扫到尾 O(n)
哈希查找：    seen.containsKey(7) → 几乎瞬间 O(1)

四类高频问法对号入座：

题目信号	哈希怎么用	典型题
两个数配对、补数	Map<值, 下标>	两数之和
判断/统计字符频次	Map<字符, 计数> 或长度 26 的数组	字母异位词
元素是否重复出现	HashSet 去重	存在重复元素
一段连续区间求和为 K	前缀和 + Map<和, 次数>	和为 K 的子数组

跟着做

步骤 1：LeetCode 242「有效的字母异位词」（简单）

给定两个只含小写字母的字符串 s 和 t，判断它们是否由相同的字母（连同每个字母的个数）组成，比如 anagram 和 nagaram 是，rat 和 car 不是。

思路：字母只有 26 种，用一个长度 26 的计数数组，s 里出现就 +1，t 里出现就 -1，最后全为 0 就是异位词。

class Solution {
    public boolean isAnagram(String s, String t) {
        if (s.length() != t.length()) {
            return false; // 长度不同，连比都不用比
        }
        int[] count = new int[26];
        for (int i = 0; i < s.length(); i++) {
            count[s.charAt(i) - 'a']++;
            count[t.charAt(i) - 'a']--;
        }
        for (int c : count) {
            if (c != 0) {
                return false;
            }
        }
        return true;
    }
}

逐点讲：s.charAt(i) - 'a' 把字母 a～z 映射成下标 0～25，这是处理小写字母题的常用技巧。时间 O(n)，空间 O(1)（数组长度固定 26，不随输入增长）。

如果字符范围是 Unicode，就改用 HashMap<Character, Integer>，写法一样，只是 key 从整数下标换成字符。

步骤 2：LeetCode 1「两数之和」（简单）

给定整数数组 nums 和目标 target，返回和为 target 的两个数的下标，题目保证恰有一个解。

关键转变：不要写双重循环枚举每一对。对当前元素 nums[i]，真正要回答的问题是「target - nums[i] 之前出现过吗？在哪个下标？」——这正是一次哈希查询。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexByValue = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int complement = target - nums[i];
            if (indexByValue.containsKey(complement)) {
                return new int[]{indexByValue.get(complement), i};
            }
            indexByValue.put(nums[i], i); // 先查后存，避免同一个元素用两次
        }
        return new int[]{};
    }
}

逐点讲：循环不变量是「map 里存着 i 之前所有元素的值和下标」。先查询、再放入当前元素，顺序不能反，否则 target 恰好是某个数两倍时会错拿自己。时间 O(n)，空间 O(n)。

步骤 3：LeetCode 49「字母异位词分组」（中等）

给一个字符串数组，把互为字母异位词的字符串分到同一组，例如输入 ["eat","tea","tan","ate","nat","bat"]，输出三组。

思路：互为异位词的字符串，排序后结果相同。那么「排序后的字符串」就是天然的分组 key，用 Map<key, 同组原字符串列表> 即可。

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>();
        for (String s : strs) {
            char[] chars = s.toCharArray();
            Arrays.sort(chars);
            String key = new String(chars);
            // key 第一次出现时新建列表，然后把原字符串加进去
            groups.computeIfAbsent(key, k -> new ArrayList<>()).add(s);
        }
        return new ArrayList<>(groups.values());
    }
}

逐点讲：computeIfAbsent 是 HashMap 的常用方法——key 存在就取已有 value，不存在就用后面的函数造一个放进去。时间 O(n·k log k)，其中 n 是字符串个数、k 是最长字符串长度（排序耗时）；空间 O(n·k)。

进阶：若字符串只含小写字母，可以把 key 从「排序串」换成「字母计数序列」（如 a2b1...），省掉排序，时间降到 O(n·k)。面试时先给排序版（简单不易错），再口述这个优化即可拿满。

讲清楚要点

1. 哈希表存的是「历史」：几乎所有数组 + 哈希题都是单次遍历 + 维护一个关于「已处理元素」的 map/set，核心动作是「先查历史，再更新历史」。
2. key 怎么设计是灵魂：两数之和的 key 是值、value 是下标；异位词的 key 是排序串或计数串。想清楚「什么东西相等就该归为一类」，key 就出来了。
3. 字符范围小用数组，范围大用 HashMap：26 个小写字母用 int[26]，常数空间且更快；Unicode 字符再上 Map。
4. 哈希是期望 O(1)，不是绝对 O(1)：极端哈希碰撞时会退化，但工程和面试中按平均 O(1) 分析即可。
5. 先写主流程再补边界：空数组、单元素、重复值、负数，提交前过一遍这些用例。

你可能会懵的地方

• 为什么 HashMap 查找能是 O(1)？不用比较吗？ 它用哈希函数把 key 直接换算成数组下标，像查座位号一样直接定位，不需要和其他元素逐个比较。碰撞（两个 key 算出同一位）时才用链表/树处理，正常情况很少。

• containsKey 和 get 分两步写，会不会查两次？ 有轻微重复开销，但代码最清晰。追求一步到位可用 Integer idx = map.get(complement); if (idx != null)，注意值确实可能为 null 时的歧义。

• 异位词为什么排序后一定相同？ 排序只重排字符顺序，不改变每个字符的个数。两个字符串字符构成完全相同，排完序的序列自然逐位相等。

• computeIfAbsent 看不懂，能用普通写法吗？ 能：groups.putIfAbsent(key, new ArrayList<>()); groups.get(key).add(s); 两行等价，先保证写对。

• 什么时候前缀和才派上用场？ 题目问「连续子数组的和满足某条件有多少个」时（如 LeetCode 560）。单点配对、频次统计用不到它，别硬套。

错法对照

错法	问题	正解
两数之和用双重循环	O(n²)，n=10⁵ 时超时	哈希一次遍历 O(n)
先 put 当前元素再查 complement	可能把同一个元素用两次	先查后存
用 new int[256] 处理所有字符	对 Unicode 不够用	小写字母用 26，其余用 HashMap
异位词只比较字母集合（Set）	漏掉字母个数，如 aab 与 abb	用计数而非集合
分组时把排序串加入结果	结果要求的是原字符串	key 用排序串，列表里存原串

卡点急救

1. 提交报数组越界（负下标）：检查 char - 'a' 的输入是否真的只有小写字母；含空格、大写或其他字符时要么归一化，要么换 HashMap。
2. 频次题用 Map 写得绕：记住一句——map.merge(ch, 1, Integer::sum) 或 map.put(ch, map.getOrDefault(ch, 0) + 1)，计数增一只用这一行。
3. 想不出 key 怎么设计：回到题目问「什么条件下两个输入要被当成同一类」，把这个条件的「规范化表示」作为 key（排序、计数、差值等）。

面试常问

• 两数之和如果数组有序，怎么做？还需要哈希吗？ 有序就可以用左右双指针向中间靠拢（下一课内容），时间 O(n)、空间 O(1)，比哈希省空间。也可以固定一个数，对另一个数做二分，O(n log n)。

• 哈希表什么情况下会退化？怎么避免？ 大量 key 哈希到同一个桶时，链表变长，查询退化到 O(n)（Java 8 后桶会树化为 O(log n)）。使用不可变、分布均匀的 key，负载因子超过阈值时 HashMap 会自动扩容，一般不用手动干预。

• 如何统计一个文件里每个单词出现次数？ 典型词频统计：逐行读取、按分隔符切词，Map<String,Integer> 累加，等价于字母异位词的计数套路。工程上数据量大时走 MapReduce / 流式分组，但单机思路完全相同。

自测三问

1. 不用哈希时两数之和是什么复杂度？哈希把哪一步从 O(n) 降到了 O(1)？
2. 判断字母异位词的两种 key（排序串、计数串）各自的复杂度是多少？
3. 「先查后存」和「先存后查」在两数之和里会造成什么不同结果？

小结一句话

数组负责遍历、哈希负责瞬间查找，凡是「配对、频次、去重」类信号，先想单次遍历加一张哈希表能不能把 O(n²) 压成 O(n)。

延伸

• 巩固练习：LeetCode 217 存在重复元素、LeetCode 560 和为 K 的子数组、LeetCode 347 前 K 个高频元素
• 本课题目都可以直接在本站在线判题平台提交，留意平台返回的边界失败用例
• 下一课预告：双指针——当数据有序或要在数组两端做文章时，两个下标如何配合解决三数之和、盛最多水的容器