数组与哈希题型：扫描、计数与映射

学“数组与哈希题型：扫描、计数与映射”时，我走过的弯路可以概括成一句话：我做数组题时习惯上来就写双重循环，看到重复元素、频次统计也想不到先用一张映射表保存已经见过的信息。问题不在于知识点有多难，而在于我一开始只盯着结果，没有看到它在维护什么关系。下面是我重新补这块基础时留下的笔记。

数组和哈希表经常一起出现：数组负责提供线性扫描顺序，哈希表负责保存已经见过的信息。很多看起来需要双重循环的问题，本质上都可以通过“扫描 + 记忆”降到线性复杂度。

数组与哈希的分工

数组与哈希题型地图

图：数组负责遍历，哈希表负责记忆补数、频次、位置或集合

常见组合方式如下：

问题类型	哈希表保存什么	典型题
是否出现过	`Set<Value>`	存在重复元素
值到位置	`Map<Value, Index>`	两数之和
值到次数	`Map<Value, Count>`	多数元素、字母异位词
前缀值到位置	`Map<Prefix, FirstIndex>`	最长和为 k 的子数组
前缀值到次数	`Map<Prefix, Count>`	和为 k 的子数组个数

两数之和：保存补数关系

暴力做法是枚举两个数，复杂度 O(n²)。哈希做法是一边扫描，一边检查之前是否出现过补数。

int[] twoSum(int[] nums, int target) {
    Map<Integer, Integer> index = new HashMap<>();
    for (int i = 0; i < nums.length; i++) {
        int need = target - nums[i];
        if (index.containsKey(need)) {
            return new int[]{index.get(need), i};
        }
        index.put(nums[i], i);
    }
    return new int[]{-1, -1};
}

这里哈希表保存的是“之前出现过的值在哪里”。注意先查再放，避免同一个元素被使用两次。

频次统计：把值变成计数

当题目出现“出现次数”“是否同构”“是否异位词”时，第一反应应该是频次表。

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 x : count) {
        if (x != 0) return false;
    }
    return true;
}

如果字符范围固定，用数组比 HashMap 更简单也更快；如果 key 范围很大或不是整数，再使用哈希表。

前缀和 + 哈希：记录历史状态

如果题目问“连续子数组和为 k 的个数”，仅有前缀和还不够，因为我们要知道之前有多少个前缀满足 pre[j] = pre[i] - k。

int subarraySum(int[] nums, int k) {
    Map<Integer, Integer> count = new HashMap<>();
    count.put(0, 1);
    int prefix = 0;
    int ans = 0;
    for (int x : nums) {
        prefix += x;
        ans += count.getOrDefault(prefix - k, 0);
        count.put(prefix, count.getOrDefault(prefix, 0) + 1);
    }
    return ans;
}

这里 count.put(0, 1) 很关键，它表示从数组开头开始的一段也可以被统计到。

最长连续序列：只从起点出发

数组无序时，排序可以做，但复杂度是 O(n log n)。用 HashSet 可以做到平均 O(n)。

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)) continue;
        int cur = x;
        while (set.contains(cur)) cur++;
        best = Math.max(best, cur - x);
    }
    return best;
}

关键点是只从连续段起点开始扩展。如果每个元素都向后扩展，会退化成重复扫描。

工程场景

数组 + 哈希不仅是刷题技巧，在真实开发中也很多：

批量数据去重。
日志里统计错误码次数。
判断一批 ID 是否已经存在。
把列表转成 Map，避免循环里重复查找。
做接口聚合时按 ID 合并多个来源的数据。

我的分析

哈希表很强，但不能滥用。数据量小、范围固定时，数组计数更轻；需要有序遍历时，HashMap 又不合适，可能要 TreeMap；需要并发访问时，还要考虑 ConcurrentHashMap。

做这类题，我会先问：我要保存的是“出现过”“次数”“位置”，还是“历史前缀状态”。这个问题想清楚，代码就不会乱。

面试题

HashMap 平均 O(1) 的前提是什么？
为什么两数之和要先查再放？
前缀和哈希为什么要初始化 0 -> 1？
字符统计什么时候用数组，什么时候用哈希表？
哈希表能不能解决所有查找问题？为什么？