给定一个整数nums和一个整数k的数组，返回其总和等于k的连续子数组的总数 [英] Given an array of integers nums and an integer k, return the total number of continuous subarrays whose sum equals to k

问题描述

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'''

''' here when the target < 0 i want to break the loop and for example if there is array 1,2,3 and my target is 2 i will go to the loop first add 1 next again add 2 which is not possible so i want to break the next checking series and want to start from 2'''

推荐答案

您可以尝试使用前缀想法和 defaultdict()来解决此子数组总和问题.优雅而高效.它取决于 prefix 总和的想法，代码易于遵循，您可以尝试使用不同的数据运行.在 dc [v] 中，我们存储所有前缀和num.的上一个将值v前缀为sum.然后循环并在数组中查看是否有新的num. w 的值满足 w-v等于k 的值，然后我们得到一个新的计数(对).

You could try to use the prefix idea and defaultdict() to solve this Subarray Sum problem more elegantly and efficiently. It's depending on the prefix sum idea, the code is easy to follow, you could try to run it with different data. In the dc[v] we store all prefix sum, the num. of prev. prefix sum with value v. Then it loops and the array to see if new num. w coming has value that satisfies w-v equal k then we got a new count(pair).

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

这篇关于给定一个整数nums和一个整数k的数组，返回其总和等于k的连续子数组的总数的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！