和为 k 的子数组----前缀和+哈希表算法

前缀和算法知识点引用整理

如果不了解前缀和的原理的请参考以下链接,这些都是我从不懂这个算法看到懂的资料相信对大家也会有所帮助:
五分钟学算法：前缀和系列:有图有文字的说明 易于理解原理

前缀和差值的最通俗解释:对前缀和中的差值进行了举例说明

详细的讲解:一步一步讲解如何实现和解决–和为 k 的子数组 这一道题 虽然最终的解题方法略微有些繁琐 但是分析和解决问题的思路很值得借鉴

题目

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。

示例1：

输入:nums = [1,1,1], k = 2

输出: 2

解释: 此题 [1,1] 与 [1,1] 为两种不同的情况

示例2：

输入:nums = [1,2,3], k = 3

输出: 2

提示

1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

解题代码(python3)

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
    	#创建count用于统计和为k的数组个数 sum用于保存数组的和
        count=sum=0
        #预先在哈希表中创建 0:1键值对
        hash={0:1}
        #遍历数组
        for n in nums:
        	#统计当前数的和
            sum+=n
            #检测sum-k是否存在哈希表中 若存在获取value值当作个数,若不存在获取默认值0
            count+=hash.get(sum-k,0)
            #将sum值存入哈希表
            hash[sum]=hash.get(sum,0)+1
        return count
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

完成后的思考

根据上面参考的大佬们的代码和思路 完成并通过了测试用例
但是还有一些疑惑:

疑惑

关于哈希表中的value值 每次确认了哈希表中存在键后加一 但是统计次数的时候直接全部加上了 这不会导致下次sum-k的值计算的时候重复计算吗?

解决疑惑

比如测试用例改为:
nums=[1,1,1,1,0,0,0,0]
k=2
结果为7
代码中增加打印哈希表的内容

        for n in nums:
            sum+=n
            count+=hash.get(sum-k,0)
            hash[sum]=hash.get(sum,0)+1
            #增加打印 查看哈希表中的内容
			print("key:",sum-k," value:",hash.get(sum-k,0))
1
2
3
4
5
6

打印结果如下:
sum: 1 sum-k: -1 value: 0
sum: 2 sum-k: 0 value: 1
sum: 3 sum-k: 1 value: 1
sum: 4 sum-k: 2 value: 1
sum: 4 sum-k: 2 value: 1
sum: 4 sum-k: 2 value: 1
sum: 4 sum-k: 2 value: 1
sum: 4 sum-k: 2 value: 1
根据代码 count+=hash.get(sum-k,0) 的意思 如果我某一次的sum-k值为4的话 那么下一次计算到这个值时count直接会+5
所以我再次加入一个数 满足sum-k值为4的条件 所以这个值是2

于是再次修改用例:
nums=[1,1,1,1,0,0,0,0,2]
k=2
此时的结果为12 确实是直接+5
新增的打印结果如下:
sum: 6 sum-k: 4 value: 5
这么一看,再加上前缀和差值的最通俗解释对于差值的解释就明白了,value中保存的是sum-k值为起点,sum为终点的路径数,测试用例中就是从0到2的数组个数
所以直接加上value的值完全是一点问题都没有.

总结

这个疑惑还是因为对于前缀和中的哈希表的键值所代表的含义理解不完全所导致的