博客

前缀和算法：

可以O(1)时间下得到子数组的和。




python

class Solution:
    def subarraySum(self, nums: List[int], k: int):
        n = len(nums)
        preNum = [0] * (n+1)
        needs = {0:1}
        count = 0

        for i in range(n):
            preNum[i+1] = preNum[i] + nums[i]
        
        for i in range(1, n+1):
            target = preNum[i] - k

            if target in needs.keys():
                count += needs[target]

            if preNum[i] not in needs.keys():
                needs[preNum[i]] = 1
            else:
                needs[preNum[i]] += 1
        
        return count