560. 和为K的子数组

官方最优解

• 前缀

ans = 0 
for i in range(len(nums)):sum = 0for j in range(i, -1, -1):# j: i -> 0,相当于计算前i个数的和# 在计算前i个数的和的过程中，可能会出现sum == k的情况sum += nums[j]if sum == k :count += 1
但这种方法时间复杂度高，为O(n^2)
换种思路，既然sum==k是出现在计算j的过程中
我们转换为都计算前缀，然后把结尾为i的前缀 - 结尾为j的前缀，
如果结果等于k那就说明存在这样的子数组
即 k = pre[i] - pre[j]
也即pre[j] = pre[i] - k
那我们就统计每种前缀和的个数就好了，并在统计的过程中查找是否有pre[j]的存在即可

class Solution(object):def subarraySum(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""hash = collections.defaultdict(int)pre_i = 0count = 0hash[0] = 1n = len(nums)for i in range(n):pre_i += nums[i]# 统计所有的前缀和的个数# hash[sum] += 1  这个不能放这里,因为nums=[1], k =0时，会输出1# 需要考虑一种情况，就是sum - k = 0，说明此时二者相等啊，# 那count就应该+1, 所以就必须要设定hash[0] = 1# 其他情况sum-k in hash，说明前j-1段是存在的，# 那就需要统计hash表里面的键为sum-k的值if (pre_i - k) in hash: count += hash[pre_i - k]# 统计所有的前缀和的个数hash[pre_i] += 1return count# nums=[1,1,1]    k=2

• 同理，我也可以试试 后缀解法

class Solution(object):def subarraySum(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""n = len(nums)hash = collections.defaultdict(int)post_i = 0count = 0hash[0] = 1for i in range(n-1, -1, -1):post_i += nums[i]if post_i - k  in hash:# 说明post_j是在hash里面的# count += 1# 加的应该是post_j对应的值的个数count += hash[post_i - k]hash[post_i] += 1return count

超出时间限制！！！
我的方法是$O(n^2)$啊，应该也还行吧

• 这个是从前面往末尾加，相当于计算后缀

class Solution(object):def subarraySum(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""# nums = sorted(nums) # 因为人家说的子串必须是连续的，所以不能sortedn = len(nums)ans = 0for i in range(n):s = nums[i]j = i+1if s == k:ans += 1# while s != k and j < n : #不能有s!=k,因为也许下一个也是0，不影响结果# nums = [1, -1, 0], k = 0while j < n:s += nums[j]j += 1if s == k:ans += 1return ans

官网解法1

也超时了，因为它的时间复杂度也是$O(n^2)$

• 从后面往前面加，相当于计算前缀

class Solution(object):def subarraySum(self, nums, k):""":type nums: List[int]:type k: int:rtype: int"""count = 0 for i in range(len(nums)):s = 0 for j in range(i, -1, -1):s += nums[j]if s == k:count += 1return count