和为K的子数组出现了多少个

思路：前缀和＋哈希表（记录前缀和出现次数）

和为k，将k视为一个区间。子数组，要想到区间和，然后想到前缀和。prefix_sum=(prefix_sum-k)+k

def subArraySum(k,nums): cnt=0 prefix_sum=0 mp={0:1} #初始化前缀和为0的子数组出现次数为1 for i in range(len(nums)): prefix_sum+=nums[i] if prefix_sum-k in mp: #关键 cnt+=mp[prefix_sum-k] mp[prefix_sum]=mp.get(prefix_sum,0)+1 print(cnt) def main(): k=int(input()) line=input() nums=list(map(int,line.split())) subArraySum(k,nums) if __name__=="__main__": main()

也可以这样写，先处理前缀和数组，这样就不用像上面那样初始化mp了

cnt=0 mp={} prefix=[0]*(len(nums)+1) for i in range(len(nums)): prefix[i+1]=prefix[i]+nums[i] for j in prefix: if j-k in mp: cnt+=mp[j-k] mp[j]=mp.get(j,0)+1 print(cnt)