560. 和为K的子数组

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

示例  :

输入:nums = [1,1,1], k = 2
输出: 2 ,  [1,1] 与 [1,1] 为两种不同的情况。

 思路1：字典记录前缀和

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        num_times = collections.defaultdict(int)
        num_times[0] = 1
        cur_sum = 0 
        res = 0
        for i in range(len(nums)):
            cur_sum += nums[i]  
            if cur_sum - k in num_times:  
                res += num_times[cur_sum - k]
            num_times[cur_sum] += 1
        return res

思路2：动态规划（OJ超时）

class Solution: #超时
    def subarraySum(self, nums: List[int], k: int) -> int:
        N = len(nums)
        dp = [0]*N
        dp[0] = 0 if nums[0]!=k else 1
        for i in range(1,N):
            temp = 0
            flag = 0
            for j in range(i,-1,-1):
                temp+=nums[j]
                if temp == k:
                    flag += 1
            dp[i] = dp[i-1]+flag
        return dp[-1]