↓Skip to main content
  1. Posts/

LeetCode-560 和为 K 的子数组

·1 min·
Table of Contents

LeetCode-560 和为 K 的子数组 #

Solution 1 #

寻找和为 K 的子数组等价成寻找差为 K 的前缀和对. 注意 $0$ 是默认的前缀和, 对应左端点为 0 的子数组. 哈希计数.

代码如下:

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        presum = list(accumulate(nums))
        ans = 0
        book = defaultdict(int)
        book[0] = 1
        for x in presum:
            ans += book[x - k]
            book[x] += 1
        return ans