0560：和为 K 的子数组（★）

力扣第 560 题

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 104
• -1000 <= nums[i] <= 1000
• -107 <= k <= 107

相似问题：

• 0001：两数之和
• 0523：连续的子数组和
• 0713：乘积小于 K 的子数组
• 0724：寻找数组的中心下标
• 0974：和可被 K 整除的子数组（1675 分）
• 1658：将 x 减到 0 的最小操作数（1817 分）
• 2090：半径为 k 的子数组平均值（1358 分）
• 2219：数组的最大总分

分析

• 求任意子数组的和，容易想到前缀和
• 得到前缀和数组 P，问题即是找 P 的两个元素使其差为 k
• 遍历用哈希表计数即可

解答

1
2
3
4
5
6
7
8

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

92 ms