leetcode-和为K的子数组

和为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

前缀和

class Solution:
    def subarraySum(self, nums: list[int], k: int) -> int:
        prefix = [0] * (len(nums) + 1)
        result = 0

        for i in range(len(nums)):
            prefix[i + 1] = prefix[i] + nums[i]

        for i in range(len(nums)):
            for j in range(i + 1, len(nums) + 1):
                if prefix[j] - prefix[i] == k:
                    result += 1

        return result

前缀和+hash

def subarraySum(self, nums: list[int], k: int) -> int:
    prefix = 0
    result = 0
    count = {0: 1}

    for num in nums:
        prefix += num

        if prefix - k in count:
            result += count[prefix - k]

        if prefix in count:
            count[prefix] += 1
        else:
            count[prefix] = 1

    return result

prefix[i] = nums[0] + nums[1] + … + nums[i-1]
sum(i, j) = prefix[j] - prefix[i]

利用前缀和，避免重复计算子数组和，复杂度：O(n²) 但还有优化空间

核心优化 → 前缀和 + 哈希表
当遍历到 prefix[j] 时，只需要知道之前有没有出现过 prefix[j] - k
用哈希表 count_map 记录每个前缀和出现次数
遍历一次即可统计所有子数组数量

prefix = 0
# 空前缀，避免漏掉从开头开始的子数组，就像是我们使用前缀数组的时候开头设置一个空
# 在数组开头前，我们假设已经有一个前缀和为 0
count_map = {0:1} 
result = 0

for num in nums:
    # 表示当前前缀和
    prefix += num
    # 判断是否存在子数字满足条件
    if prefix - k in count_map:
        # 如果有多个子数组满足条件加多次
        result += count_map[prefix - k]
    # 记录子数组出现次数
    count_map[prefix] = count_map.get(prefix, 0) + 1