【算法笔记】力扣热题100（LeetCode hot-100）560. 和为 K 的子数组

力扣热题100（LeetCode hot-100）之 560. 和为 K 的子数组

本文主要记录算法思路，着急要答案的同学可以直接跳转到最后的代码。

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。示例 1：输入：nums = [1,1,1], k = 2
输出：2
示例 2：输入：nums = [1,2,3], k = 3
输出：2提示：1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

题解

这个问题，一般怎么解？

思路：

使用 前缀和 和 哈希表 的方法。

1. 定义一个哈希表 map，用于存储前缀和及其出现的次数。
2. 初始化前缀和 preSum 为 0，前缀和为 0 的个数为 1。
3. 遍历数组，计算当前的前缀和 preSum。
4. 如果 map 中存在 preSum - k，说明存在一个子数组的和为 k，更新计数器 count。
5. 更新哈希表中前缀和的个数

答案

class Solution {public int subarraySum(int[] nums, int k) {final var map = new HashMap<Integer, Integer>();// 初始化，前缀和为0的个数为1map.put(0, 1);int preSum = 0;int count = 0;for (int num : nums) {preSum += num;if (map.containsKey(preSum - k)) { // 如果存在前缀和为preSum - k的子数组，那么这个子数组到当前位置的和为kcount += map.get(preSum - k);}// 更新前缀和为preSum的子数组个数map.put(preSum, map.getOrDefault(preSum, 0) + 1);}return count;}
}