🔥个人主页：Milestone-里程碑
❄️个人专栏: <<力扣hot100>> <<C++>><<Linux>>
<<Git>><<MySQL>>
🌟心向往之行必能至
题目解读
给定一个整数数组nums和一个整数k，我们需要统计并返回数组中和为 k 的连续子数组的个数。
- 子数组必须是连续且非空的，比如
[1,1]是[1,1,1]的一个子数组，但[1,2]不是。 - 注意数组中可能包含负数，这会让滑动窗口等方法失效，而前缀和则能很好地应对这种情况。
暴力解法（超时预警）
最直观的思路是枚举所有可能的子数组，计算它们的和并判断是否等于k。
cpp
// 暴力解法（超时） int subarraySum(vector<int>& nums, int k) { int count = 0; for (int i = 0; i < nums.size(); ++i) { int sum = 0; for (int j = i; j < nums.size(); ++j) { sum += nums[j]; if (sum == k) count++; } } return count; }这个方法的时间复杂度是O(n²)，在nums长度达到 2×10⁴ 时会直接超时，必须寻找更优解。
最优思路：前缀和 + 哈希表
我们可以用「前缀和」来优化这个问题。
前缀和定义
我们定义preSum[i]为数组前i个元素的和，那么：preSum[i] = nums[0] + nums[1] + ... + nums[i-1]
对于子数组nums[j...i-1]，它的和可以表示为：sum = preSum[i] - preSum[j]
我们的目标是找到所有满足preSum[i] - preSum[j] = k的j，也就是：preSum[j] = preSum[i] - k
哈希表优化
我们可以用一个哈希表hash来记录每个前缀和出现的次数，这样在遍历到i时，只需要查询hash[preSum[i] - k]就能得到满足条件的j的数量，从而把时间复杂度降到 O (n)。
初始化技巧：
- 我们需要把
hash[0] = 1作为初始值，这是为了处理preSum[i] = k的情况（此时j = 0，对应子数组从开头到i-1）。
完整代码实现
cpp
class Solution { public: int subarraySum(vector<int>& nums, int k) { unordered_map<int, int> hash; hash[0] = 1; // 初始化前缀和 0 出现 1 次 int preSum = 0; int count = 0; for (int num : nums) { preSum += num; // 查找有多少个前缀和等于 preSum - k if (hash.find(preSum - k) != hash.end()) { count += hash[preSum - k]; } // 将当前前缀和加入哈希表 hash[preSum]++; } return count; } };代码解析
- 初始化哈希表：
hash[0] = 1是为了处理子数组从第一个元素开始的情况。 - 遍历计算前缀和：每次遍历
num时，更新当前的前缀和preSum。 - 查询哈希表：如果
preSum - k存在于哈希表中，说明存在j使得preSum[i] - preSum[j] = k，此时把对应的次数加到count中。 - 更新哈希表：将当前前缀和
preSum加入哈希表，记录它出现的次数。
复杂度分析
- 时间复杂度：O (n)，我们只需要遍历数组一次，哈希表的查询和插入操作都是 O (1)。
- 空间复杂度：O (n)，哈希表最多存储 n 个不同的前缀和。
总结
这道题的核心是利用「前缀和」将子数组和的问题转化为前缀和的差值问题，再通过「哈希表」快速统计符合条件的前缀和出现次数，从而实现线性时间复杂度的解法。这种思路在很多子数组和相关的题目中都非常有用。
)
)
