560. 和为 K 的子数组
type
status
date
slug
summary
tags
category
difficulty
icon
password
560. 和为 K 的子数组
给你一个整数数组
nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。子数组是数组中元素的连续非空序列。
示例 1：
示例 2：
提示：
1 <= nums.length <= 2 * 104
1000 <= nums[i] <= 1000
107 <= k <= 107
解题思路：
这道题目要求统计和为k的子数组个数，我们可以使用前缀和 + 哈希表的方法来解决。以下是具体思路：
1. 前缀和数组
首先构建前缀和数组 s，其中 s[i] 表示 nums[0] 到 nums[i-1] 的元素和。这样，任意区间 [i,j] 的和就可以通过 s[j+1] - s[i] 得到。
2. 哈希表的应用
使用哈希表 map 记录每个前缀和出现的次数。对于当前遍历到的前缀和 s[i]，如果存在一个前缀和等于 s[i] - k，那么说明存在一个子数组的和为 k。
3. 具体实现步骤
- 初始化哈希表，空数组的和为0出现1次，即 map[0] = 1
- 遍历前缀和数组，对于每个位置 i：
- 查找是否存在前缀和为 s[i] - k 的位置，如果存在，将其出现次数累加到结果中
- 更新当前前缀和 s[i] 在哈希表中出现的次数
4. 时间复杂度分析
- 时间复杂度：O(n)，其中 n 是数组长度。我们只需要遍历一次数组。
- 空间复杂度：O(n)，需要哈希表来存储前缀和。
5. 举例说明
以示例 nums = [1,1,1], k = 2 为例：
- 构建前缀和数组 s = [0,1,2,3]
- 遍历过程中的哈希表变化：
- i=1时：查找s[1]-k=1-2=-1的个数，map={0:1,1:1}
- i=2时：查找s[2]-k=2-2=0的个数，找到1个，map={0:1,1:1,2:1}
- i=3时：查找s[3]-k=3-2=1的个数，找到1个，map={0:1,1:1,2:1,3:1}
最终返回找到的2个子数组：[1,1] 和 [1]。
- 作者:Episkey
- 链接:https://episkey.top/article/subarray-sum-equals-k
- 声明:本文采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。
