python-3.x - 给定一个整数数组 nums 和一个整数 k，返回总和等于 k ​​的连续子数组的总数

Question

def subarraySum(self, nums: List[int], k: int) -> int:
    count = 0
    target = k
    self.cal(nums,target,count,k)
    return count
def cal(nums,target, count,k):
    if target == 0:
        count = count+1
        target = k
        return count,target
    if target<0:
        return 
        
    for i in range(len(nums)):
        self.cal(nums[:i]+nums[i+1:],target-nums[i],count,k)

''' 这里当目标 < 0 我想打破循环，例如如果有数组 1,2,3 并且我的目标是 2 我将进入循环首先添加 1 再添加 2 这是不可能的所以我想打破下一个检查系列并想从 2''' 开始

标签： python-3.xbacktrackingrecursive-backtracking

Answer 1

您可以尝试使用该prefix想法并defaultdict()更优雅有效地解决此子数组求和问题。这取决于prefix总和的想法，代码很容易理解，您可以尝试使用不同的数据运行它。在dc[v]我们存储所有前缀和，num。上一个 以值 v 为总和前缀。然后它循环和数组以查看是否有新的 num。w来的值满足，w-v equal k然后我们得到一个新的计数（对）。

from collections import defaultdict
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dc = defaultdict(int)
        sum_ = 0
        dc[0] = 1
        result = 0
        for n in nums:
            sum_ += n
            if sum_ - k in dc:
                result += dc[sum_ - k]
            dc[sum_] += 1
        return result