560. 和为K的子数组（中等）- LeetCode

题目描述

自己解法

解法一：暴力求解，时间复杂度$O(n^2)$O(n2)，空间复杂度$O(1)$O(1)：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        ans = 0
        L = len(nums)
        for i,val in enumerate(nums):
            remain = k - val
            if remain == 0:
                ans += 1
            for j in range(i+1,L):
                remain -= nums[j]
                if remain == 0:
                    ans += 1
        return ans

解法二：哈希表+前缀和求解，时间复杂度$O(n)$O(n)，空间复杂度$O(n)$O(n)。

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        mp = {0:1}
        ans,pre = 0,0
        for i,val in enumerate(nums):
            pre += val
            if pre - k in mp:
                ans += mp[pre-k]
            mp[pre] = mp.get(pre,0) + 1
        return ans 

官方解答参考：链接。