[2025-09-25] Leetcode 560. 和为 K 的子数组（未满足）

题目

560. 和为 K 的子数组
给你一个整数数组 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

我的代码（Python）

version 1

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        results = [[nums[0]]]
        resultCnt = 0
        for i in range(1, len(nums)):
            results.append([nums[i]] + [x + nums[i] for x in results[i - 1]])
        for i in range(len(results)):
            resultCnt += results[i].count(k)
        return resultCnt

最基础的暴力解法，不出意外地内存爆掉了。

version 2

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        result = []
        resultCnt = 0
        for i in range(len(nums)):
            for j in range(i):
                result[j] += nums[i]
                if result[j] == k:
                    resultCnt += 1
            if nums[i] == k:
                resultCnt += 1
            result.append(nums[i])
        return resultCnt

Version 1中的缓存是没必要的，于是做了优化，结果是时间爆掉了。即使把计数改成resultCnt += result.count(k)也是一样。

version 3

import numpy as np
class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        result = np.array([])
        resultCnt = 0
        for i in range(len(nums)):
            result = np.append(result, 0)
            result += nums[i]
            resultCnt += np.count_nonzero(result == k)
        return resultCnt

换成numpy时间勉强通过了，但还是很差，看来还是思路问题。

点评

官方没有Python代码答案，根据官方的思路写下来是这样的：

class Solution:
    def subarraySum(self, nums: List[int], k: int) -> int:
        resultsMap = {0:1}
        resultCnt = 0
        currSum = 0
        for i in range(len(nums)):
            currSum += nums[i]
            if currSum - k in resultsMap:
                resultCnt += resultsMap[currSum - k]
            if currSum in resultsMap:
                resultsMap[currSum] += 1
            else:
                resultsMap[currSum] = 1
        return resultCnt

好吧，始终还是没有把标准库列入算法基本操作的思路，所以根本没往这个方向想。