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

LeetCode 560. 和为K的子数组超详细题解（前缀和+哈希表最优解法）

news 2026/3/26 11:59:10

LeetCode 560. 和为K的子数组超详细题解（前缀和+哈希表最优解法）

🏷️ 标签：前缀和、哈希表、数组、中等、经典面试题

📊 难度：中等|📝 题目编号：560|🗂️ 题型：数组 / 前缀和

一、题目描述

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

子数组定义：数组中元素的连续非空序列，要求元素连续、不能断开。

二、示例演示

示例 1

输入：nums = [1,1,1], k = 2 输出：2 解释：符合条件的子数组为 [1,1]（下标0-1）、[1,1]（下标1-2），共2个。

示例 2

输入：nums = [1,2,3], k = 3 输出：2 解释：符合条件的子数组为 [1,2]、[3]，共2个。

三、数据范围与约束

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

注意：数组元素可正可负，不能用滑动窗口（滑动窗口仅适用于全正/全负数组），必须用前缀和+哈希表解法。

四、解题思路分析

1. 暴力解法（超时，仅供理解）

最直观的思路是枚举所有起点和终点，计算区间和判断是否等于k。

外层循环枚举子数组起点i
内层循环枚举子数组终点j，累加求和
时间复杂度：O(n²)，n=2e4时会超时，无法通过全部用例

2. 最优解法：前缀和 + 哈希表

核心公式

定义前缀和preSum[i]表示数组前i个元素的和（下标从0到i-1），即：

preSum[i]=nums[0]+nums[1]+...+nums[i−1]preSum[i] = nums[0] + nums[1] + ... + nums[i-1]preSum[i]=nums[0]+nums[1]+...+nums[i−1]

那么，下标从j到i-1的子数组和为：

preSum[i]−preSum[j]=kpreSum[i] - preSum[j] = kpreSum[i]−preSum[j]=k

变形可得：

preSum[j]=preSum[i]−kpreSum[j] = preSum[i] - kpreSum[j]=preSum[i]−k

解题逻辑

遍历数组，维护当前的前缀和current_sum
用哈希表记录每个前缀和出现的次数
每遍历到一个位置，查找哈希表中是否存在current_sum - k
若存在，将对应的次数累加到答案中
初始化哈希表：{0:1}，处理前缀和本身等于k的情况

为什么要初始化 {0:1}

当current_sum == k时，current_sum - k = 0，代表从数组开头到当前位置的子数组和恰好为k，这是一个合法答案，需要提前存入0出现1次。

五、满分代码（Python）

严格遵循题目指定代码格式，代码简洁高效，附带详细注释，可直接提交。

fromtypingimportListclassSolution:defsubarraySum(self,nums:List[int],k:int)->int:# 哈希表：key=前缀和，value=出现次数pre_map={0:1}current_sum=0count=0fornuminnums:# 更新当前前缀和current_sum+=num# 查找需要的目标前缀和target=current_sum-k# 若存在，累加次数iftargetinpre_map:count+=pre_map[target]# 将当前前缀和存入哈希表pre_map[current_sum]=pre_map.get(current_sum,0)+1returncount

六、代码详解

1. 变量说明

pre_map：哈希表，存储前缀和及其出现次数，初始{0:1}
current_sum：遍历过程中实时计算的前缀和
count：统计符合条件的子数组个数，最终返回值
target：需要查找的目标前缀和，即 current_sum - k

2. 执行流程（以示例1 nums=[1,1,1], k=2 为例）

初始化：pre_map={0:1}, current_sum=0, count=0
遍历第一个1：current_sum=1，target=1-2=-1（不存在），pre_map[1]=1
遍历第二个1：current_sum=2，target=0（存在，次数1），count=1，pre_map[2]=1
遍历第三个1：current_sum=3，target=1（存在，次数1），count=2，pre_map[3]=1
遍历结束，返回count=2，与示例结果一致

3. 关键细节

先查找，再存入哈希表，避免当前元素重复使用
数组含负数、零，依然适用，通用性强
用get方法获取键值，避免键不存在报错

七、复杂度分析

时间复杂度：O(n)，仅遍历数组一次，哈希表查找和插入均为O(1)均摊复杂度
空间复杂度：O(n)，最坏情况下所有前缀和都不同，哈希表存储n+1个键值对

八、常见易错点

误用滑动窗口：数组含负数时，窗口和不具备单调性，滑动窗口失效
忘记初始化{0:1}：漏掉从数组开头到当前位置的合法子数组
先存入再查找：导致当前前缀和被重复计算，答案偏大
暴力解法超时：数据量较大时，O(n²)无法通过测评

九、题型总结

本题是前缀和的经典入门题，也是面试高频考点，核心思想是利用前缀和将区间和问题转化为哈希表查找问题，把时间复杂度从O(n²)优化至O(n)。