[Medium]LeetCode#560. 和为K的子数组
题目原地址
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
输入: nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。
说明 :
数组的长度为 [1, 20,000]。
数组中元素的范围是 [-1000, 1000] ，且整数 k 的范围是 [-1e7, 1e7]。
最简单的方案，两次遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| func subarraySum(nums []int, k int) int {
//两次遍历
res := 0
n := len(nums)
left := 0
l := 0
for i := 0; i < n; {
left += nums[i]
if left == k {
res++
}
if l < n && i == n-1 {
i = l
left = 0
l++
}
i++
}
return res
}
|
另一种解题方案，就是hash
1
2
3
4
5
6
7
8
9
10
11
12
| func subarraySum(nums []int, k int) int {
//使用hash的方法
res, sum := 0, 0
numMap := make(map[int]int, len(nums))
numMap[0] = 1
for _, v := range nums {
sum += v
res += numMap[sum-k]
numMap[sum]++
}
return res
}
|
执拗前行