LeetCode热题100--560.和为K的子数组（前缀和）--中等

1.题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

2. 题解

class Solution {public int subarraySum(int[] nums, int k) {int n = nums.length;int[] s = new int[n+1];for(int i = 0; i < n; i++){s[i+1] = s[i] + nums[i];}int ans = 0;Map<Integer,Integer> cnt = new HashMap<>(n+1);for (int sj : s){ans += cnt.getOrDefault(sj - k, 0);cnt.merge(sj, 1, Integer::sum);}return ans;}
}

3. 解析

出自这位老师：灵茶山艾府：前缀和+哈希表：从两次遍历到一次遍历，附变形题（Python/Java/C++/Go/JS/Rust）

第1部分：初始化变量和前缀和数组

int n = nums.length;
int[] s = new int[n+1];

• int n = nums.length;：获取输入数组nums的长度，赋值给n。
• int[] s = new int[n+1];：创建一个长度为n+1的前缀和数组s。前缀和数组用于存储从数组开头到当前位置的累加和。

第2部分：填充前缀和数组

for(int i = 0; i < n; i++){s[i+1] = s[i] + nums[i];
}

• 使用一个循环从i=0遍历到nums.length-1，计算前缀和。
• s[0]初始化为0，表示前缀和数组的第一个元素是0。
• 对于每个索引i（0 ≤ i < n），将当前nums的值加到s[i+1]中。这样，s[i+1]就记录了从nums[0]到nums[i]的累加和。

第3部分：初始化答案变量

int ans = 0;

• int ans = 0;：用于累计符合条件子数组的数量。

第4部分：创建哈希表并初始化

Map<Integer,Integer> cnt = new HashMap<>(n+1);

• 创建一个容量为n+1的HashMap，键值类型是Integer。
• hashmap的作用是统计每个前缀和出现的次数。这里预先分配了n+1个空间。

第5部分：遍历前缀和数组

for (int sj : s){ans += cnt.getOrDefault(sj - k, 0);cnt.merge(sj, 1, Integer::sum);
}

• 遍历s数组中的每一个元素sj。
• 对于每个sj，首先查找键值对(sj - k)在map中出现的次数，并将这个次数加到ans中。这一步的作用是找到所有以当前前缀和sj为结尾且子数组和等于k的子数组数量。
• 然后更新哈希表cnt：将键sj的出现次数增加1。

第6部分：返回答案

return ans;

最终返回累计的符合条件子数组的数量ans。