LeetCode 题解工作台
和为 K 的子数组
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。 子数组是数组中元素的连续非空序列。 示例 1： 输入： nums = [1,1,1], k = 2 输出： 2 示例 2： 输入： nums = [1,2,3], k = 3 输出： 2 提示： 1 …
3
题型
6
代码语言
3
相关题
当前训练重点
中等 · 数组·哈希·扫描
答案摘要
我们定义一个哈希表 ，用于存储数组 的前缀和出现的次数。初始时，我们将 的值设为 ，表示前缀和 出现了一次。 我们遍历数组 ，计算前缀和 ，然后将 $\textit{cnt}[s - k]$ 的值累加到答案中，并将 的值增加 。
Interview AiBoxInterview AiBox 实时 AI 助手，陪你讲清 数组·哈希·扫描 题型思路
题目描述
给你一个整数数组 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:
cnt = Counter({0: 1})
ans = s = 0
for x in nums:
s += x
ans += cnt[s - k]
cnt[s] += 1
return ans
复杂度分析
| 指标 | 值 |
|---|---|
| 时间 | complexity is O(n) since each element is processed once and hash map lookups are constant on average. Space complexity is O(n) due to storing prefix sums in the hash map. |
| 空间 | Depends on the final approach |
面试官常问的追问
外企场景- question_mark
Checks if candidate considers brute-force inefficiency with nested loops.
- question_mark
Looks for use of prefix sum combined with hash lookup to count subarrays.
- question_mark
Observes whether edge cases like negative numbers and zero sums are handled correctly.
常见陷阱
外企场景- error
Forgetting to initialize hash map with 0:1, causing missed subarrays starting at index 0.
- error
Using nested loops which lead to O(n^2) performance and timeouts.
- error
Neglecting negative numbers or zeros which can invalidate prefix sum assumptions.
进阶变体
外企场景- arrow_right_alt
Return all subarrays themselves instead of just the count using a similar prefix sum map.
- arrow_right_alt
Find the longest subarray with sum equal to k, adjusting the map to store earliest indices.
- arrow_right_alt
Count subarrays with sum less than or equal to k, modifying lookup logic to handle ranges.