当前位置 博文首页 > 努力的小菜鸟的博客:leetcode刷题——560、和为k的子数组(前缀
??直接暴力遍历的话会超时。因此使用前缀和思想和哈希表结合的方式去解这道题。具体解释来说:
??1、程序中定义前缀和数组prefix_sum,prefix_sum[i]用于记录数组nums[0]~nums[i]的和;
??2、我们需要找到数组中和为k的连续子数组,用前缀和数组来解释的话就是:在数组中找是否存在下标i和j,i小于j,使得prefix_sum[j]-prefix_sum[i]=k。
??3、在遍历数组nums的过程中,对于当前的元素item而言,计算出对应的前缀和prefix_sum[j],那么求解是否有以item结尾的连续子数组就等价于判断是否存在一个前缀和为prefix[j]-k。
??4、为何要结合哈希表?题目中指出需要找到“连续的子数组的个数”,为了返回这个个数,我们使用哈希表来处理。定义hashtable,其中的key就是我们求得的前缀和,value则是对应的前缀和出现的次数。
??具体到程序中,借鉴前缀和的思想,我们只需要定义一个变量始终记录当前索引处的前缀和prefix_sum,对这一前缀和做以下几种情况的处理:
??1、判断前缀和prefix_sum的值是否为k,是的话将待返回的个数cnt+1;
??2、判断哈希表hashtable中是否有一项的key为prefix_sum-k,有的话更新cnt的值为cnt+hashtable[prefix_sum-k]
??接下来要做的就是将prefix_sum保存下来,那么保存时就会有两种情况:
??1、hashtable中有一项的值为prefix_sum,表明我们已经找到过若干连续子数组的和prefix_sum,此时需要更新对应的value;
??2、hashtable中没有任何一项的key为prefix_sum,此时将(key=prefix_sum, value=1)送入哈希表即可。
class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
# 基于前缀和思想,采用哈希表处理
hashtable = {}
prefix_sum = cnt = 0 # prefix_sum用于记录前缀和,cnt记录符合条件的子数组的个数
for val in nums:
prefix_sum += val
# 如果当前的前缀和等于k,将cnt+1
if prefix_sum == k:
cnt +=1
# 检查哈希表中是否存在prefix_sum-k
if prefix_sum-k in dic:
cnt += hashtable[prefix_sum-k]
# 如果prefix_sum存在于哈希表,则更新对应的value;否则设置value为1
if prefix_sum in hashtable:
hashtable[prefix_sum] += 1
else:
hashtable[prefix_sum] = 1
return cnt
1 | 2 | 3 | 4 | -2 | 2 | 1 | 2 |