前缀和 + 哈希表

在算法刷题中，子数组相关问题常常令人头疼，尤其是涉及到子数组和的条件判断时。不过，有一类经典解法——前缀和结合哈希表，能巧妙攻克这类难题。今天就结合三道力扣题目，深入讲讲这种方法的运用，带你吃透子数组问题的解题思路。
 

一、核心思路：前缀和 + 哈希表的魔力
 

1. 前缀和是什么？
 
前缀和，简单说就是数组中从起始位置到当前位置的元素和。假设数组是  nums ，前缀和数组  preSum  满足  preSum[i] = nums[0] + nums[1] + ... + nums[i-1]  。这样，子数组  nums[i...j]  的和就能用  preSum[j+1] - preSum[i]  快速算出，避免了重复累加，提升效率。
 
2. 哈希表的作用
 
哈希表（ unordered_map ）主要用来记录前缀和出现的次数或者首次出现的索引。遇到相同前缀和时，结合条件判断，就能快速找出符合要求的子数组，把嵌套循环的高复杂度问题，优化到线性复杂度。
 

下面结合具体题目，一步步拆解怎么用这俩“神器”解题。
 

二、实战演练：三道题掌握核心技巧
 

题目 1：525. 连续数组（找 0 和 1 数量相等的最长子数组）
 

问题分析
 
给定二进制数组，要找 0 和 1 数量相等的最长连续子数组。直接暴力枚举所有子数组，判断 0 和 1 数量，复杂度是 O(n^2) ，数据量大时肯定超时。得换更聪明的办法！
 
转化与思路
 
把数组里的  0  看成  -1  ， 1  保持  1  。这样，“0 和 1 数量相等的子数组”就转化为“子数组和为 0 的子数组”（因为  -1  和  1  数量相等时，和为 0 ）。
 
用前缀和  sum  遍历累加转换后的值，同时用哈希表  hash  记录每个前缀和第一次出现的索引。一旦遇到相同的前缀和，说明这两个索引之间的子数组和为 0 ，计算长度更新最大值即可。
 
代码解析
 

class Solution {
public:int findMaxLength(vector<int>& nums) {unordered_map<int, int> hash; hash[0] = -1;  // 初始化，前缀和为0时索引设为-1，方便计算开头的子数组int sum = 0, ret = 0; for (int i = 0; i < nums.size(); i++) { sum += nums[i] == 0 ? -1 : 1;  // 0转-1，1不变，计算当前前缀和if (hash.count(sum)) {  // 之前出现过相同前缀和ret = max(ret, i - hash[sum]);  // 计算子数组长度，更新最大值} else {  // 没出现过，记录第一次出现的索引hash[sum] = i; }}return ret; }
};

 
 
- 初始化  hash[0] = -1 ：假设前缀和为 0 时在索引 -1 位置，比如数组  [0,1]  ，遍历到  i=1  时， sum=0  ， i - hash[0] = 1 - (-1) = 2  ，刚好是正确结果长度。
- 前缀和转换：把 0 转成 -1 ，让问题转化为找和为 0 的子数组，巧妙利用前缀和特性。
- 哈希表判断：通过判断前缀和是否重复，快速定位符合条件的子数组，把复杂度降到 O(n) 。
 

题目 2：974. 和可被 K 整除的子数组（统计和能被 K 整除的子数组数目）
 

问题分析
 
给定整数数组和整数  k  ，统计和能被  k  整除的非空子数组数目。直接枚举子数组计算和，复杂度太高，得用前缀和 + 哈希表优化。
 
同余定理与思路
 
根据同余定理：若  (a - b) % k == 0  ，则  a % k == b % k  。所以，只要找到前缀和  sum[i]  和  sum[j]  （ i < j  ）模  k  余数相同，那么子数组  nums[i...j-1]  的和就能被  k  整除。
 
用哈希表记录每个余数出现的次数，遍历前缀和时，计算当前余数，累加之前相同余数的次数，就是新增的符合条件的子数组数目。
 
代码解析
 

class Solution {
public:int subarraysDivByK(vector<int>& nums, int k) {unordered_map<int, int> hash; hash[0] = 1;  // 前缀和模k余0的情况，初始有1次（空前缀）int sum = 0, ret = 0; for (auto e : nums) { sum += e; int t = (sum % k + k) % k;  // 处理负数余数，保证结果非负if (hash.count(t)) {  // 之前有相同余数ret += hash[t];  // 累加次数}hash[t]++;  // 更新当前余数的次数}return ret; }
};

 
 
- 处理负数余数： (sum % k + k) % k  这一步很关键。因为  sum % k  可能是负数（比如  sum=-1  ， k=5  时， -1 % 5 = -1  ），加上  k  再取模，能把余数转成非负，方便哈希表存储和判断。
- 初始化  hash[0] = 1 ：空前缀的和是 0 ，模  k  余 0 ，对应子数组从开头开始的情况（比如数组第一个元素就能被  k  整除时，需要算上这种情况 ）。
- 累加次数逻辑：每次遇到相同余数，说明之前有若干前缀和满足条件，这些前缀和到当前位置的子数组和能被  k  整除，所以直接累加次数，高效统计结果。
 

题目 3：560. 和为 K 的子数组（统计和为 K 的子数组数目）
 

问题分析
 
给定数组和整数  k  ，统计和为  k  的连续子数组个数。同样，暴力枚举复杂度高，用前缀和 + 哈希表优化。
 
思路推导
 
子数组和为  k  ，即  preSum[j] - preSum[i] = k  ，变形得  preSum[i] = preSum[j] - k  。所以，遍历前缀和时，只要在哈希表中找到  preSum[j] - k  出现的次数，就是以当前位置结尾的、和为  k  的子数组数目。
 
代码解析
 

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int, int> hash; hash[0] = 1;  // 前缀和为0的情况，初始有1次（空前缀）int sum = 0, ret = 0; for (auto x : nums) { sum += x;  // 计算当前前缀和if (hash.count(sum - k)) {  // 找是否有前缀和为 sum - kret += hash[sum - k];  // 累加次数}hash[sum]++;  // 记录当前前缀和出现的次数}return ret; }
};

 
 
-  hash[0] = 1  的作用：当子数组从开头开始就满足和为  k  时（比如  nums[0] = k  ）， sum - k = 0  ，这时候  hash[0] = 1  就能正确统计到这种情况。
- 找  sum - k  的逻辑：通过判断之前是否有前缀和为  sum - k  ，快速算出以当前元素结尾的、和为  k  的子数组数量，把复杂度从 O(n^2) 降到 O(n) 。
 

三、总结：这类题的通用解题步骤
 

1. 问题转化：根据题目条件，把原问题转化为前缀和的条件判断（比如和为 0、和模 k 余数相同、和为 K 等 ）。
2. 哈希表初始化：根据转化后的条件，初始化哈希表。通常要考虑前缀和为 0 的特殊情况（对应子数组从开头开始的场景 ）。
3. 遍历计算前缀和：逐个元素计算前缀和，过程中用哈希表记录前缀和的出现情况（次数或首次索引 ）。
4. 条件判断与统计：根据转化后的条件，在哈希表中查找对应值，统计符合条件的子数组数目或更新最长长度。
 
这三道题虽然具体条件不同，但核心思路都是前缀和 + 哈希表，通过巧妙转化问题，利用哈希表快速查找的特性，把高复杂度的枚举问题优化成线性遍历，效率大幅提升。掌握这种思路后，再遇到子数组和相关的问题，就能快速想到解法，轻松应对啦！
 
如果你在刷题时遇到类似子数组问题，不妨试试这种方法，多练习几次，就能熟练掌握啦～ 觉得有收获的话，欢迎点赞、收藏，也可以留言分享你的刷题心得呀！