【LeetCode 热题 100】560. 和为 K 的子数组——（解法二）前缀和+哈希表
Problem: 560. 和为 K 的子数组
题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
【LeetCode 热题 100】560. 和为 K 的子数组——（解法一）前缀和+暴力
整体思路
这段代码旨在以高效的方式解决 “和为k的连续子数组” 的问题。与前一个 O(N^2) 的解法相比，此版本利用了 前缀和（Prefix Sum） 与 哈希表（HashMap） 相结合的强大技巧，将时间复杂度优化到了线性级别。
算法的核心思想基于一个关键的数学关系：如果 nums[0...j] 的前缀和为 preSum_{j+1}，nums[0...i-1] 的前缀和为 preSum_i，那么子数组 nums[i...j] 的和就是 preSum_{j+1} - preSum_i。
我们想要找到满足 preSum_{j+1} - preSum_i = k 的 (i, j) 对的数量。将这个方程变形，我们得到 preSum_i = preSum_{j+1} - k。
这个变形后的公式是算法的基石。它告诉我们：对于当前计算出的每一个前缀和 preSum_{j+1}，我们只需要找到在此之前，有多少个 preSum_i 恰好等于 preSum_{j+1} - k。 这个数量，就是以当前 j 位置为结尾、和为 k 的子数组的数量。
算法的具体执行步骤如下：
-
数据结构选择与初始化：
- 使用一个哈希表
cnt来存储【前缀和 -> 出现次数】的映射。这使得我们能够以 O(1) 的平均时间复杂度查询某个前缀和历史出现过几次。 - 初始化
preSum = 0（代表空数组的前缀和）和ans = 0（最终结果计数器）。
- 使用一个哈希表
-
单次遍历与动态计算：
- 算法只需遍历一次
nums数组。在循环的每一步，针对当前元素x：
a. 记录历史状态：在更新preSum之前，先将当前的preSum值（即不包含x的前缀和）存入哈希表cnt。这一步非常关键，它确保了我们总是在查找“过去”的前缀和。例如，cnt.merge(preSum, 1, Integer::sum)的作用是：如果preSum已存在，其计数值加 1；如果不存在，则插入(preSum, 1)。
b. 更新当前状态：将preSum加上当前元素x，得到新的前缀和。
c. 查找并累加结果：根据核心公式，在哈希表中查找键为preSum - k的值。cnt.getOrDefault(preSum - k, 0)会返回之前preSum - k这个前缀和出现过的次数。将这个次数累加到ans上。
- 算法只需遍历一次
-
处理边界情况：
- 这个算法巧妙地处理了从索引 0 开始的子数组。在第一次循环开始时，
preSum是 0。代码首先会将(0, 1)放入cnt中。这样，如果后续某个preSum正好等于k，那么preSum - k就是 0，算法就能从cnt中查到(0, 1)，正确地将这个从头开始的子数组计入结果。
- 这个算法巧妙地处理了从索引 0 开始的子数组。在第一次循环开始时，
通过这种方式，算法在一次遍历中同时建立历史记录和进行查找，将问题从“枚举子数组”转化为了“查找特定前缀和”，实现了巨大的效率提升。
完整代码
class Solution {/*** 计算和为 k 的连续子数组的个数（优化版）。* @param nums 整数数组* @param k 目标和* @return 和为 k 的连续子数组的数量*/public int subarraySum(int[] nums, int k) {// preSum: 动态计算的当前前缀和int preSum = 0;// ans: 最终结果，和为 k 的子数组数量int ans = 0;// cnt: 哈希表，用于存储 {前缀和 -> 出现次数} 的映射Map<Integer, Integer> cnt = new HashMap<>();// 遍历数组中的每个元素for (int x : nums) {// 步骤 1: 记录当前的前缀和（在加上 x 之前）。// 这是算法最巧妙的一步。将 preSum（代表 nums[0...i-1] 的和）存入哈希表。// 这样，当我们处理完 nums[i] 后，就能查找之前出现过的前缀和。// `merge` 方法：如果 preSum 不存在，放入 (preSum, 1)；如果存在，将其值加 1。// 第一次循环时，preSum=0，这会将 (0, 1) 放入 map，用于处理从索引 0 开始的子数组。cnt.merge(preSum, 1, Integer::sum);// 步骤 2: 更新前缀和，包含当前元素 xpreSum += x;// 步骤 3: 查找并累加结果。// 根据公式 preSum_j - preSum_i = k => preSum_i = preSum_j - k// 我们在哈希表中查找 `preSum - k` 出现过几次，这个次数就是// 以当前元素为结尾、和为 k 的子数组的数量。// getOrDefault 确保如果没找到，则返回 0。ans += cnt.getOrDefault(preSum - k, 0);}// 返回最终统计的数量return ans;}
}
时空复杂度
时间复杂度：O(N)
- 循环：算法的核心是一个
for循环，它遍历nums数组中的每一个元素。如果数组长度为N，这个循环将执行N次。 - 循环内部操作：
cnt.merge()：HashMap的merge操作，在平均情况下的时间复杂度是 O(1)。preSum += x：基本的算术运算，时间复杂度是 O(1)。cnt.getOrDefault()：HashMap的get操作，在平均情况下的时间复杂度是 O(1)。
- 综合分析：整个算法由
N次 O(1) 的操作组成。因此，总的时间复杂度是N * O(1)= O(N)。
空间复杂度：O(N)
- 主要存储开销：算法使用了一个哈希表
cnt来存储前缀和及其出现的频率。 - 空间大小：在最坏的情况下，
nums数组中所有元素计算出的前缀和都是唯一的。例如，nums = [1, 2, 3, 4, ...]。在这种情况下，哈希表cnt需要存储N个不同的前缀和，因此其大小会增长到N。 - 其他变量：
preSum,ans,x等变量只占用常数级别的空间，即 O(1)。
综合分析：算法所需的额外空间主要取决于哈希表的大小，它与输入数组的长度 N 成线性关系。因此，空间复杂度为 O(N)。
参考灵神