560.和为K的子数组
一、问题描述
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续子数组的个数。
示例:
plaintext
输入:nums = [1,1,1], k = 2
输出: 2
解释: 连续子数组 [1,1] 和 [1,1] 的和分别为 2 和 2。二、方案一：暴力法
1、思路
暴力法是最直观的方法。对于数组中的每个元素，我们尝试找出所有以该元素为起始点的子数组，并计算它们的和。如果和等于 k，我们就增加计数。
2、代码实现
go
func subarraySum(nums []int, k int) int {
count, n := 0, len(nums)
for start := 0; start < n; start++ {
sum := 0
for end := start; end < n; end++ {
sum += nums[end]
if sum == k {
count++
}
}
}
return count
}3、复杂度分析
- 时间复杂度：O(n^2)，其中 n 是数组的长度。我们需要双重循环来遍历所有可能的子数组。
- 空间复杂度：O(1)，不需要额外的空间。
三、方案二：前缀和 + 哈希表
1、思路
我们可以使用前缀和的概念来优化上述解法。前缀和数组 prefixSums 的每个元素 prefixSums[i] 表示数组 nums 从第一个元素到第 i 个元素的和。利用前缀和，我们可以将子数组的和转化为两个前缀和的差。
「j..i子数組和为 k」这个条件我们可以转化为 pre[i]- pre[j-1]= k，简单移项可得符合条件的下标 j 需要满足 pre[j-1] == pre[i]一 k。所以我们考点以 i 结尾的和为 k 的连续子数組个数时，只要统计有多少个前缀和为 pre[i]一 k 即可。
为了快速计算子数组的和，我们可以使用哈希表来存储每个前缀和出现的次数。对于每个前缀和 prefixSums[i]，我们查询哈希表中 prefixSums[i] - k 的数量，这表示有多少个子数组的和为 k。
2、代码实现
go
func subarraySum(nums []int, k int) int {
m := map[int]int{}
m[0] = 1
count, pre := 0, 0
for i := 0; i < len(nums); i++ {
pre += nums[i]
if _, ok := m[pre-k]; ok {
count += m[pre-k]
}
m[pre] += 1
}
return count
}3、复杂度分析
- 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历数组一次，对于每个元素，我们在哈希表中的操作时间复杂度为 O(1)。
- 空间复杂度：O(n)，我们需要一个哈希表来存储前缀和及其出现的次数。
四、总结
| 方案 | 时间复杂度 | 空间复杂度 |
|---|---|---|
| 暴力法 | O(n^2) | O(1) |
| 前缀和 + 哈希表 | O(n) | O(n) |
在处理这类问题时，使用前缀和和哈希表可以显著提高效率，特别是当数组较大时。