给定一个整数数组和一个整数 k,你需要找到该数组中和为 k 的连续的子数组的个数。

示例 1 :

1
2
输入:nums = [1,1,1], k = 2
输出: 2 , [1,1] 与 [1,1] 为两种不同的情况。

法一——暴力

两重循环,对每一个数字,从它开始往后,不断地累加,然后和k进行对比,这应该是最简单的想法了,但是我做这种题还是有点晕

1
2
3
4
5
6
7
8
9
10
11
def subarraySum(nums, k):
length = len(nums)
count = 0
for i in range(length):
sum = 0
for j in range(i, length):
sum += nums[j]
if sum == k:
count += 1

return count

法二——hashtables

思路就是不断地求和,然后判断 cur_sum - k 是否已经计算过了

将前缀和放入哈希表,哈希表的设计为:key是前缀和,value是前缀和出现的次数。
如果当前要存入的前缀和sum,使得(sum - k)也在哈希表中时,则使用count累加哈希表中(sum - k)出现的次数,然后再将该sum放入哈希表中。这里的count与sum的添加次序不能调换,主要是为了处理k为0的情况。

1
2
3
4
5
6
7
8
9
def subarraySum(self, nums, k):
result, cur_sum = 0, 0
sum_dict = {0:1}
for num in nums:
cur_sum += num
if cur_sum - k in sum_dict:
result += sum_dict[cur_sum - k]
sum_dict[cur_sum] = sum_dict.get(cur_sum, 0) + 1
return result

go实现的代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
func subarraySum(nums []int, k int) int {
count := 0
sumMap := map[int]int{0:1,}
sum := 0
for _, num := range nums {
sum += num
if sumMap[sum - k] > 0 {
count += sumMap[sum - k]
}
sumMap[sum]++
}

return count
}