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