一、题目描述
给你一个整数数组nums和一个整数k，请你统计并返回该数组中和为k的子数组的个数。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2示例 2：
输入：nums = [1,2,3], k = 3 输出：2提示：
- 1≤nums.length≤2×1041 \le nums.length \le 2 \times 10^41≤nums.length≤2×104
- −1000≤nums[i]≤1000-1000 \le nums[i] \le 1000−1000≤nums[i]≤1000
- −107≤k≤107-10^7 \le k \le 10^7−107≤k≤107
⚠️ 重点：数组包含负数！不能用滑动窗口双指针！
二、暴力解法分析（超时）
最容易想到的思路：枚举子数组起点和终点，累加区间和判断是否等于k。
两层循环，时间复杂度O(n2)O(n^2)O(n2)。
当 n 达到 2e4 时，运算量高达 4e8，一定会超时，无法通过。
三、前缀和核心思想
前缀和pre[i]：数组从下标 0 加到下标 i 的总和。
区间[j+1,i][j+1, i][j+1,i]的和公式：
sum=pre[i]−pre[j]sum = pre[i] - pre[j]sum=pre[i]−pre[j]
题目要求区间和等于 k：
pre[i]−pre[j]=kpre[i] - pre[j] = kpre[i]−pre[j]=k
变形得到：
pre[j]=pre[i]−kpre[j] = pre[i] - kpre[j]=pre[i]−k
含义：遍历到 i 的时候，只要前面已经出现过前缀和等于pre[i] - k，就对应一组合法连续子数组。
四、前缀和 + 哈希表优化思路
哈希表作用：记录每个前缀和出现的次数
初始化：mp[0] = 1
作用：处理pre[i] == k的场景，也就是从数组开头到 i 的子数组满足条件。
遍历流程：
- 当前前缀和加上当前元素
- 查询
pre - k是否存在哈希表，存在则把对应次数加到答案 - 将当前前缀和更新进哈希表，计数+1
✅ 顺序不能颠倒：先查询，再存入哈希表，避免重复使用当前位置
五、C++ 代码实现
#include <unordered_map> #include <vector> using namespace std; class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> mp; mp[0] = 1; int pre = 0, res = 0; for (int x : nums) { pre += x; if (mp.find(pre - k) != mp.end()) { res += mp[pre - k]; } mp[pre]++; } return res; } };六、Python 代码实现
from collections import defaultdict from typing import List class Solution: def subarraySum(self, nums: List[int], k: int) -> int: cnt = 0 pre = 0 hashmap = defaultdict(int) hashmap[0] = 1 for x in nums: pre += x if pre - k in hashmap: cnt += hashmap[pre - k] hashmap[pre] += 1 return cnt七、复杂度分析
- 时间复杂度：(O(n))(O(n))(O(n))，数组一次遍历，哈希表查询平均(O(1))(O(1))(O(1))
- 空间复杂度：(O(n))(O(n))(O(n))，哈希表最多存储 n 个前缀和
八、高频易错点总结
- 数组存在负数，前缀和不单调，不能用双指针滑动窗口
- 必须初始化
mp[0] = 1，很多人漏掉这个条件导致样例不通 - 操作顺序：先查
pre-k，再更新哈希表，不能反过来 - 相同前缀和需要累加次数，不是只记录是否存在
