Problem: 560. 和为 K 的子数组
题目：给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
【LeetCode 热题 100】560. 和为 K 的子数组——（解法二）前缀和+哈希表
整体思路
这段代码的目的是计算一个整数数组 nums 中，和为特定值 k 的 连续子数组 的个数。例如，对于 nums = [1, 1, 1] 和 k = 2，连续子数组 [1, 1] 有两个，它们分别从索引 0 和 1 开始，所以结果是 2。
该算法采用了一种基于 前缀和（Prefix Sum） 的暴力枚举法。其核心逻辑步骤如下：
-
预处理：计算前缀和
- 算法首先创建了一个比原数组
nums长一个单位的数组sum。sum[i]被设计用来存储nums数组中从索引 0 到i-1的所有元素的累加和。 sum[0]初始化为 0，作为计算的基准。- 通过一次遍历，计算出所有前缀和，即
sum[i+1] = sum[i] + nums[i]。 - 核心优势：一旦拥有了前缀和数组，我们就可以在 O(1) 的时间内计算出任意连续子数组
nums[i...j]的和。其计算公式为sum[j+1] - sum[i]。这避免了在每次检查子数组时都进行重复的求和计算，将一个潜在的 O(N^3) 算法优化到了 O(N^2)。
- 算法首先创建了一个比原数组
-
枚举所有子数组并校验
- 接下来，代码使用两层嵌套的循环来枚举出所有的连续子数组。
- 外层循环的变量
j代表子数组的 结束索引。 - 内层循环的变量
i代表子数组的 起始索引。 - 通过
for (j=0..n-1)和for (i=0..j)的组合，可以不重不漏地生成所有可能的(i, j)对，即所有连续子数组。 - 对于每一个由
(i, j)定义的子数组，利用前缀和数组，通过sum[j+1] - sum[i]快速得到其和。 - 将计算出的和与目标值
k进行比较。如果相等，则将计数器ans加一。
-
返回结果
- 在遍历完所有可能的子数组后，
ans中就存储了最终的总数，将其返回。
- 在遍历完所有可能的子数组后，
总而言之，该算法通过预计算前缀和，然后系统地遍历所有可能的子数组端点，来解决这个问题。虽然它不是最优解法（最优解法使用哈希表，时间复杂度为O(N)），但它是一个思路清晰且正确的暴力解法。
完整代码
class Solution {/*** 计算和为 k 的连续子数组的个数。* @param nums 整数数组* @param k 目标和* @return 和为 k 的连续子数组的数量*/public int subarraySum(int[] nums, int k) {// 获取数组的长度int n = nums.length;// 创建前缀和数组 sum，长度为 n+1。// sum[i] 将存储 nums[0] 到 nums[i-1] 的和。// sum[0] = 0，作为计算的起点，代表空数组的和。int[] sum = new int[n + 1];// ans 用于累计和为 k 的子数组的数量int ans = 0;// 步骤 1: 预计算前缀和// 遍历 nums 数组，填充 sum 数组for (int i = 0; i < n; i++) {// sum[i+1] 等于前 i 个元素的和（sum[i]）加上当前元素 nums[i]sum[i + 1] = sum[i] + nums[i];}// 步骤 2: 枚举所有子数组// 外层循环确定子数组的结束索引 jfor (int j = 0; j < n; j++) {// 内层循环确定子数组的起始索引 i// i 的范围是从 0 到 j，确保 i <= jfor (int i = 0; i <= j; i++) {// 利用前缀和快速计算子数组 nums[i...j] 的和// sum[j+1] 是 nums[0...j] 的和// sum[i] 是 nums[0...i-1] 的和// 两者相减即为 nums[i...j] 的和if (sum[j + 1] - sum[i] == k) {// 如果子数组的和等于 k，计数器加 1ans++;}}}// 返回最终的计数结果return ans;}
}
时空复杂度
时间复杂度：O(N^2)
- 前缀和计算：第一个
for循环遍历nums数组一次，用于计算前缀和。这个循环执行了N次。因此，这部分的时间复杂度是 O(N)。 - 子数组枚举：
- 第二个（外层）
for循环的变量j从0到N-1，执行N次。 - 第三个（内层）
for循环的变量i从0到j。其执行次数依赖于j。 - 总的执行次数是
1 + 2 + 3 + ... + N，这是一个等差数列求和，结果为N * (N + 1) / 2。 - 因此，嵌套循环部分的复杂度为 O(N^2)。
- 第二个（外层）
- 循环内部操作：在最内层循环中，
sum[j + 1] - sum[i]和比较操作都是 O(1) 的。
综合分析：
算法的总时间复杂度由各部分相加决定：O(N) + O(N^2)。在 Big O 表示法中，我们只保留最高阶项，所以最终的时间复杂度是 O(N^2)。
空间复杂度：O(N)
- 主要存储开销：算法创建了一个名为
sum的整型数组来存储前缀和。 - 空间大小：该数组的长度是
n + 1，其中n是输入数组nums的长度。因此，它占用的空间与输入规模N成线性关系。 - 其他变量：
n,ans,i,j等变量都只占用常数级别的空间，即 O(1)。
综合分析：
算法所需的额外空间主要由前缀和数组 sum 决定。因此，空间复杂度为 O(N)。
