一. 核心痛点: 为什么暴力法必超时
当我们看到问题 要找和为k或被k整除的连续子数组时 第一反应都是双层for循环
- 时间复杂度: O(n^2)
- 核心问题: 当数组长度达到10^5时 计算量高达100亿次 必爆TLE(超时)
- 滑动窗口: 看到连续序列 也会想到使用滑动窗口 但是由于数据有正有负 不单调 故无法使用滑动窗口解决
二. 第一大神器: 前缀和
以560. 和为k的子数组为例
- 看到这道题目 直觉就是 往前找
当你站在数组中的某一个位置j时 你就想知道: 从那里(i)开始到我这儿(j) 和刚好为k?
笨办法就是一个一个往回数:
从j - 1到j吗?
从j - 2到j吗?..
这样计算量太大了
- 使用前缀和简化这个过程
计算每个位置的前缀和P
p[j]: 记录的是从起点到j位置的总距离
p[i - 1]: 记录的是从起点到i - 1位置的总距离
那么p[j] - p[i - 1]就是从i 到 j位置的距离如果这个距离等于k 那么[i, j]就是我们要找的子数组
三. 公式转化
k = p[j] - p[i - 1]
要转换为p[i - 1] = p[j] - k
为什么要进行转换???
因为当你遍历到 j 位置时 手里的已知量是 p[j]
为了找到符合条件的i
要回头一个个检查 当i = 0 1 2 …时 p[j] - p[i - 1] 是否等于k 这样做 时间复杂度又回到了O(n^2)
为解决这个问题 就引入了下一个神器哈希表
四. 第二大神器: 哈希表
构建哈希表时 key和value分别代表什么???
将想要快速找到的 设为key 要得到的结果 设为value
- key: 目标的特征(560: 固定的差值 974: 特定的余数)
- value:题目要求子数组个数 那么value就是特征出现的个数
**时间复杂度: ** 在unordered_map中 查找key的效率为O(1) 所以可以将整体时间复杂度降为O(n)
五. 小陷阱
- 在定义完unordered_map后 要进行 map[0] = 1的操作
主要为了解决: 以数组头为起点的子数组不被忽略
- 场景一: nums = [5 …] k = 5
走到下标0 sum = 5
sum - k = 5 - 5 = 0
如果不初始化map[0] = 1 那么[5]这个正确的子数组答案就被跳过了
- 场景二: nums = [1, 2, 2, …] k = 5
走到下标2时 sum = 5
sum - k = 5 -5 = 0
然后回哈希表里查找map[0] 发现查无此数 那么这个正确的子数组也被跳过了
六. 完整代码
560 和为k的子数组
classSolution{public:intsubarraySum(vector<int>&nums,intk){std::unordered_map<int,int>umap;umap[0]=1;intsum=0;intans=0;for(intx:nums){// 计算前缀和sum+=x;// 在哈希表内查找差值是否存在ans+=umap[sum-k];// 插入前缀和umap[sum]++;}returnans;}};974 和可被k整除的子数组
在 C++ 中，负数取余（如-1 % 5）结果仍为负数。为了让哈希表的 Key 统一，我们使用(sum % k + k) % k将其余数强制“转正”
classSolution{public:intsubarraysDivByK(vector<int>&nums,intk){// 区间和 子数组 优先考虑前缀和unordered_map<int,int>umap;umap[0]=1;intsum=0;intcount=0;for(intx:nums){// 计算前缀和sum+=x;// 在前面找目标值 并将结果模值转换为正数count+=umap[(sum%k+k)%k];// 要查找什么 就要插入什么umap[(sum%k+k)%k]++;}returncount;}};
