LeetCode刷题DAY 17：和为k的子数组---三猫

难度：中级 关键词：前缀和与哈希

1 题目描述

给定一个整数数组和一个整数 k，找到该数组中和为 k 的连续的子数组的个数。如：输入[1,2,3]，3，返回2。

2 题解

呵呵，这道题的提示中，写到了sum(i,j)=sum(0,j)-sum(0,i)，其中sum(i,j)表示第i个值到第j-1个值的和，一看这个，第一反应就是：呀，这不动态规划嘛！迫不及待把前几天学到的算法用起来，结果写出了一个比暴力匹配还垃圾的代码！

思路一：（¥#%@！*&）

最初想法是建立一个二维矩阵，记录sum(i,j)，当i=0时，直接求第一个到第j个数和，i！=0时根据sum(i,j)=sum(0,j)-sum(0,i)计算得出对应值。判断是否等于目标值并记录，然后输出满足条件的个数。是不是动态规划用的溜溜的！是不是很有成就感！氮素！看了官方解题才反应过来，我两层循环完全可以直接计算i到j的和，也就是最简单的暴力匹配法，完全不用什么状态转移！写了半天，不仅没有降低时间复杂度还增加了空间复杂度！口吐芬芳。。。。祭出这段代码保佑以后脑子都灵光。

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: result = 0 if len(nums) == 0: return [] st = [[0]*len(nums) for _ in range(len(nums))] for i in range(len(nums)): for j in range(i,len(nums)): if i == 0: st[i][j]=sum(nums[0:j+1]) else: st[i][j]=st[0][j]-st[0][i-1] if st[i][j]==k: result+=1 return result

思路二：前缀和与哈希

在经历了上面的失败，当我看到下面官方解题思路的时候感觉顿悟了：

建个哈希表，以位置i为键，pre[i]为值，判断有多少pre[i]-k在字典中出现即可。

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: h_map = {-1:0} result = 0 a=0 for i,item in enumerate(nums): a += item if a-k in list(h_map.values()): count=list(h_map.values()).count(a-k) result += count h_map[i]= a return result

思路优化：

上面代码虽然是正确的，但是耗时特别长，仔细看了官方解题，发现是以和为主键，以该和出现次数作为值，这样计算最终出现次数时，时间复杂度仅为O(1)。

class Solution: def subarraySum(self, nums: List[int], k: int) -> int: h_map = {0:1} result = 0 a = 0 for i in range(len(nums)): a+=nums[i] if a-k in h_map: result += h_map[a-k] if a not in h_map: h_map[a] = 1 else: h_map[a]+=1 return result ---来自腾讯云社区的---三猫