【python刷题】前缀和

def subarraySum(nums):
    preSum = [0 for _ in range(len(nums)+1)]
    for i in range(len(nums)):
        preSum[i+1] = preSum[i] + nums[i]
    return preSum

nums = [3,5,2,-2,4,1]
res = subarraySum(nums)
print(res)

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        preSum = [0 for _ in range(len(nums)+1)]
        for i in range(len(nums)):
            preSum[i+1] = preSum[i] + nums[i]
        print(preSum)
        res = 0
        for i in range(1,len(nums)+1):
            for j in range(i):
                if preSum[i] - preSum[j] == k:
                    res += 1
        return res  

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        dic = {}
        acc, res = 0, 0
        for num in nums:
            acc += num
            if acc == k: res += 1
            if acc - k in dic: res += dic[acc - k]
            dic[acc] = dic.get(acc, 0) + 1
        return res