前缀和与哈希模板：和相关问题的降维打击#

很多“子数组和”“区间和”“出现次数”类问题，如果你还在枚举所有区间，往往就慢了。前缀和加哈希的组合，常常能把 O(n^2) 优化到 O(n)。

⚡ 速记版模板#

// 模板用途：把“区间和问题”转成“两个前缀和之差 + 哈希计数”
Map<Integer, Integer> count = new HashMap<>(); // 哈希表：key=前缀和，value=该前缀和出现次数
count.put(0, 1); // 初始化：前缀和为 0 在“下标 -1 之前”出现 1 次，处理从 0 开始的子数组
int prefix = 0; // 当前扫描到位置的前缀和
for (int num : nums) { // 线性扫描数组
    prefix += num; // 更新当前前缀和
    answer += count.getOrDefault(prefix - k, 0); // 累加“之前前缀和=prefix-k”的出现次数
    count.put(prefix, count.getOrDefault(prefix, 0) + 1); // 记录当前前缀和出现次数，供后续位置使用
}

java

🎯 什么时候想到前缀和 + 哈希？#

典型信号：

子数组和等于 K
区间和是否满足某条件
需要统计某个前缀状态出现过多少次
想快速判断两个前缀之间的差值

Hot 100 里的典型题目：

💡 前缀和的本质#

定义：

prefix[i] = nums[0] + nums[1] + ... + nums[i - 1] // 前缀和定义：前 i 个元素之和（不含 nums[i]）

java

那么区间 [left, right] 的和就是：

prefix[right + 1] - prefix[left] // 任意区间和可由两个前缀和相减得到

java

🚀 模板一：子数组和等于 K#

class Solution {
    public int subarraySum(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>(); // 统计每个前缀和出现次数
        count.put(0, 1); // 边界：空前缀

        int prefixSum = 0; // 当前前缀和
        int answer = 0; // 满足和为 k 的子数组个数

        for (int num : nums) { // 逐个元素向右扩展
            prefixSum += num; // 累加到当前前缀
            answer += count.getOrDefault(prefixSum - k, 0); // 查找可与当前前缀构成和为 k 的历史前缀
            count.put(prefixSum, count.getOrDefault(prefixSum, 0) + 1); // 更新当前前缀出现次数
        }

        return answer; // 返回子数组数量
    }
}

java

关键理解：

若当前前缀和是 prefixSum
想让中间某段和为 k
就要找之前是否出现过 prefixSum - k

🚀 模板二：记录最早位置#

适合：

找最长满足条件区间
找最早出现的某种前缀状态

class Solution {
    public int longestSubarray(int[] nums) {
        Map<Integer, Integer> firstIndex = new HashMap<>(); // 记录某个前缀和第一次出现的位置
        firstIndex.put(0, -1); // 前缀和 0 视为出现在下标 -1，便于计算从 0 开始的区间

        int prefix = 0; // 当前前缀和
        int answer = 0; // 满足条件的最长长度

        for (int index = 0; index < nums.length; index++) { // 遍历每个位置
            prefix += nums[index]; // 更新前缀和
            if (!firstIndex.containsKey(prefix)) { // 只记录最早位置，才能得到最长区间
                firstIndex.put(prefix, index);
            }
            if (firstIndex.containsKey(prefix - 1)) { // 示例条件：寻找前缀差为 1 的最早位置
                answer = Math.max(answer, index - firstIndex.get(prefix - 1)); // 更新最长长度
            }
        }

        return answer; // 返回最长满足条件区间长度
    }
}

java

🚀 模板三：哈希计数 / 分组#

适合：

两数之和
字母异位词分组
高频元素统计

两数之和#

class Solution {
    public int[] twoSum(int[] nums, int target) {
        Map<Integer, Integer> indexMap = new HashMap<>(); // key=数值，value=该数值对应下标

        for (int index = 0; index < nums.length; index++) { // 单次遍历
            int need = target - nums[index]; // 当前数需要的配对值
            if (indexMap.containsKey(need)) { // 若配对值已出现，直接返回答案
                return new int[]{indexMap.get(need), index};
            }
            indexMap.put(nums[index], index); // 记录当前值及下标，供后续元素匹配
        }

        return new int[0]; // 兜底返回（按题目常见设定通常不会走到这里）
    }
}

java

字母异位词分组#

class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        Map<String, List<String>> groups = new HashMap<>(); // key=排序后的规范串，value=同组异位词列表

        for (String str : strs) { // 遍历每个原字符串
            char[] chars = str.toCharArray(); // 转字符数组以便排序
            Arrays.sort(chars); // 排序后异位词将得到相同字符序列
            String key = new String(chars); // 作为分组哈希键
            groups.computeIfAbsent(key, value -> new ArrayList<>()).add(str); // 将原串放入对应分组
        }

        return new ArrayList<>(groups.values()); // 返回所有分组结果
    }
}

java

⚠️ 易错点#

初始化漏掉 0 -> 1
- 子数组和题非常关键
更新顺序写反
- 先查再放，还是先放再查，会影响结果
把滑动窗口误用到含负数数组
- 有负数时，很多和相关问题应优先考虑前缀和 + 哈希
key 设计不稳定
- 异位词分组要保证同一类字符串映射到同一个 key

🎨 面试时怎么说#

我把问题转化成两个前缀状态之差，用哈希表记录前面出现过的前缀和或状态，这样就能在遍历过程中直接统计答案。

📌 一句话总结#

前缀和负责把区间问题改写成两个前缀的差，哈希负责把这个差值查询从线性变成常数级。