560. Subarray Sum Equals K

题目

Given an array of integers nums and an integer k, return the total number of subarrays whose sum equals to k.

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1], k = 2
Output: 2

Example 2:

Input: nums = [1,2,3], k = 3
Output: 2

Constraints:

1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

解法

from typing import List

# leetcode submit region begin(Prohibit modification and deletion)

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        size = len(nums)
        s = [0] * (size + 1)
        restDic = {}
        ans = 0
        for i, num in enumerate(nums):
            s[i + 1] = s[i] + num
            # 先判断当前位置是否可以和已有位置组成 目标子序列
            if s[i + 1] in restDic:
                ans += restDic[s[i + 1]]

            if s[i+1] == k:
                ans += 1
            restKey1 = s[i + 1] + k

            restDic[restKey1] = restDic.get(restKey1, 0) + 1


        return ans


        
# leetcode submit region end(Prohibit modification and deletion)
Solution().subarraySum(
    [0,0,0,0,0,0,0,0,0,0],
0
)

560. Subarray Sum Equals K ​

题目 ​

解法 ​

560. Subarray Sum Equals K

题目

解法