剑指 Offer II 010. 和为 k 的子数组

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

示例 1 :

输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2 :

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/QTMn0o

【穷举法】：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:

        arrayCount = 0
        for i in range(0 , len(nums)):
            tempSum = 0
            for j in range(i , -1,-1):
                tempSum += nums[j]
                if tempSum == k:
                    arrayCount +=1
        return arrayCount

 时间复杂度：O（n^2）,空间复杂度O(1) ;    python时间太长过不去

【前缀和 ＋字典】

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        # #鲁棒性检测
        #定义记录前缀和数组
        preSum = {"0":1}
        #定义记录子数组次数
        arrayCount = 0
        total = 0
        #计算数组中每一个数的前缀和
        for i in range(0,len(nums)) :                 #  0~len
            total += nums[i]                            #计算当前元素前缀和
            key = total - k                      #如何字典中有 preSum[j] = preSum[i] - k
            if  str(key) in preSum :                                   
                arrayCount += preSum[str(key)]
            #判断有不有前缀和键，有值加1 ， 没有添加
            if str(total) in preSum:
                preSum[str(total)] +=1
            else:
                preSum.setdefault(str(total),1)     #将前缀和存入字典

        return arrayCount

时间复杂度 O(n) ; 空间复杂度 O（N）

【重构版本】

class Solution:
    def subarraySum(self, nums, k):
        arrayCount = total = 0       #记录返回值 和 前缀和
        preSum = {0: 1}       #保存前缀和字典
        for i in nums:
            total += i        #计算当前元素前缀和
            arrayCount += preSum.get(total - k, 0)     #获取 pre【j】前缀和 次数，没有则 加 0
            preSum[pre_sum] = preSum.get(total, 0) + 1     #记录当前元素的前缀和， 值加1
        return arrayCount