当前位置：首页 > news >正文

LeetCode 560：和为 K 的子数组 | 前缀和与哈希表

news 2026/5/24 4:14:36

LeetCode 560：和为 K 的子数组 | 前缀和与哈希表

引言

和为 K 的子数组（Subarray Sum Equals K）是 LeetCode 第 560 题，难度为 Medium。题目要求在给定整数数组中找出连续子数组的元素和等于 K 的数量。这道题是前缀和与哈希表结合的经典案例，展示了如何将看似 O(n²) 的问题优化到 O(n) 时间复杂度。

这道题的核心挑战在于如何高效地统计和等于 K 的子数组数量。如果使用暴力枚举所有子数组，时间复杂度为 O(n²)。通过使用前缀和加哈希表的方法，我们可以在 O(n) 时间内解决这个问题，将时间复杂度降低一个数量级。

问题分析

题目描述

给定一个整数数组 nums 和一个整数 K，返回该数组中元素和等于 K 的连续子数组的数量。

例如，输入 nums = [1, 1, 1]，K = 2，输出为 2，因为子数组 [1, 1]（索引 0-1 和 1-2）的和都等于 2。输入 nums = [1, 2, 3]，K = 3，输出为 2，因为子数组 [1, 2] 和 [3] 的和都等于 3。

问题特点

这道题的关键在于"连续子数组"的要求。连续子数组意味着子数组的边界必须是连续的，这使得前缀和技术成为可能。如果不要求连续，问题就变成了计数问题，需要用不同的方法处理。

另一个挑战是如何在 O(n) 时间内统计所有和为 K 的子数组。暴力方法需要枚举所有可能的子数组起点和终点，时间复杂度为 O(n²)。前缀和加哈希表的方法可以将时间复杂度降低到 O(n)。

前缀和分析

对于连续子数组 nums[i:j]（包含 i 到 j），其和等于 prefixSum[j+1] - prefixSum[i]，其中 prefixSum[k] 是前 k 个元素的和（即 nums[0:k]）。因此，nums[i:j] 的和等于 K 当且仅当 prefixSum[j+1] - prefixSum[i] = K，即 prefixSum[i] = prefixSum[j+1] - K。

这个等式告诉我们：对于位置 j+1 的前缀和，如果存在 i 使得 prefixSum[i] = prefixSum[j+1] - K，那么以 i 为起点的子数组 nums[i:j] 的和就等于 K。因此，我们只需要统计对于每个位置，有多少个之前的前缀和等于当前前缀和减去 K。

哈希表优化

哈希表的设计

我们使用哈希表来记录每个前缀和出现的次数。哈希表的键是前缀和的值，值是该前缀和出现的次数。

在遍历数组时，对于每个位置，我们首先计算当前的前缀和 current_sum。然后，我们在哈希表中查找 key = current_sum - K 的出现次数，这个次数表示有多少个以当前位置结尾的和为 K 的子数组。

def subarraySum(nums, k): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count

初始化哈希表

哈希表初始化为 {0: 1}，表示前缀和为 0 出现了一次。这个初始化的作用是处理从数组开头开始的子数组。例如，如果子数组 nums[0:j] 的和等于 K，那么 prefixSum[j+1] - prefixSum[0] = K，即 prefixSum[j+1] = K。由于我们初始化 prefixSum[0] = 0，在处理第一个元素时，current_sum = nums[0]，我们需要检查 current_sum - K 是否等于 0（即 K 是否等于 current_sum）。如果没有初始化 {0: 1}，这种情况就无法被正确计数。

算法正确性证明

数学归纳法

我们使用数学归纳法证明算法的正确性。

基例：当处理第一个元素 nums[0] 时，current_sum = nums[0]。此时，哈希表中只有 {0: 1}。如果 nums[0] = K，那么 prefix_sum - K = 0 在哈希表中，count 加上 1，正确计数了子数组 nums[0:0]。如果 nums[0] != K，count 不变。基例成立。

归纳假设：假设在处理第 i 个元素之前，哈希表正确记录了所有前缀和 prefixSum[0:i] 出现的次数，count 正确计数了所有以第 i 个元素之前的位置结尾的和为 K 的子数组。

归纳步骤：处理第 i 个元素 nums[i] 后，current_sum = prefixSum[i+1]。根据归纳假设，此时 prefixSum[i] 已经在哈希表中。我们查找 prefix_sum - k = prefixSum[i+1] - K，如果存在某个 j < i+1 使得 prefixSum[j] = prefixSum[i+1] - K，那么子数组 nums[j:i+1] 的和等于 prefixSum[i+1] - prefixSum[j] = K。因此，将 prefix_map[prefix_sum - k] 加到 count 上，正确计数了所有以 i 结尾的和为 K 的子数组。然后我们更新 prefix_map[current_sum]，为后续的处理做准备。归纳步骤成立。

复杂度分析

时间复杂度

时间复杂度为 O(n)，因为我们只遍历数组一次，每次迭代只进行常数次的哈希表操作（查找和插入）。

空间复杂度

空间复杂度为 O(n)，在最坏情况下，哈希表需要存储 n+1 个不同的前缀和（加上初始的 0）。

代码实现

Python 实现

def subarraySum(nums, k): prefix_sum = 0 count = 0 prefix_map = {0: 1} for num in nums: prefix_sum += num count += prefix_map.get(prefix_sum - k, 0) prefix_map[prefix_sum] = prefix_map.get(prefix_sum, 0) + 1 return count

Java 实现

public int subarraySum(int[] nums, int k) { int prefixSum = 0; int count = 0; Map<Integer, Integer> prefixMap = new HashMap<>(); prefixMap.put(0, 1); for (int num : nums) { prefixSum += num; count += prefixMap.getOrDefault(prefixSum - k, 0); prefixMap.put(prefixSum, prefixMap.getOrDefault(prefixSum, 0) + 1); } return count; }

边界情况处理

空数组

当数组为空时，循环不会执行，count 保持为 0，返回 0，符合预期。

全负数数组

算法同样适用于全负数数组。前缀和可以是负数，哈希表的键可以是负数，没有问题。

全正数数组

算法同样适用。对于全正数数组，我们可以使用滑动窗口等其他方法，但前缀和加哈希表的方法同样正确。

K 为零

当 K = 0 时，算法仍然有效。此时我们需要统计和为零的子数组数量。初始的 {0: 1} 会正确处理空前缀和。

溢出问题

在 Java 等语言中，前缀和可能超出整数范围。由于 LeetCode 的测试用例通常在合理范围内，且 Python 的整数可以自动扩展，这个问题通常不需要特别处理。但在某些语言中，可能需要使用 long 类型来存储前缀和。

测试用例

def test_subarray_sum(): assert subarraySum([1, 1, 1], 2) == 2 assert subarraySum([1, 2, 3], 3) == 2 assert subarraySum([1], 0) == 0 assert subarraySum([0, 0], 0) == 3 assert subarraySum([-1, -1, 1], 0) == 1 assert subarraySum([1, 2, 3], 0) == 0 print("所有测试用例通过！")