力扣热题100刷题-subString-560-和为 K 的子数组

560. 和为 K 的子数组

题意

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

---

思路

易错点 / 卡点

• 负数存在：数组中可能包含负数，这意味着子数组的和不具有单调性。即使当前和已经大于 k，加上一个负数后仍可能等于 k。因此，不能简单地用滑动窗口来优化。

• O(n^2) 超时：最直观的暴力解法是枚举所有子数组的起点和终点，计算其和，时间复杂度为 O(n^3) 或优化后的 O(n^2)，在数据量较大时会超时。

• 第一想法： 通过两层循环枚举所有连续子数组。外层循环固定子数组的右端点 i，内层循环枚举左端点 j，计算 [j, i] 区间的和。

• 为什么不行： 时间复杂度为 O(n^2)，当 nums 数组的长度很大时，会导致性能问题，无法通过所有测试用例。

• 最终解法：前缀和 + 哈希表 这是解决此类问题的经典优化方法。
  1. 定义 pre[i] 为 nums[0..i-1] 的元素和。那么，任意连续子数组 nums[j..i] 的和就可以表示为 pre[i+1] - pre[j]。
  2. 我们要求的是 pre[i+1] - pre[j] == k。
  3. 将这个等式变形为 pre[j] = pre[i+1] - k。
  4. 这个等式是本题解法的关键。它的含义是：对于当前遍历到的位置 i，我们只需要找到在它之前，有多少个位置 j 的前缀和 pre[j] 恰好等于 pre[i+1] - k。
  5. 我们可以使用一个哈希表（HashMap）来记录每个前缀和值出现的次数。哈希表的 key 是前缀和的值，value 是该前-缀和值已经出现过的次数。
  6. 我们从左到右遍历数组，计算当前的前缀和 current_sum。在哈希表中查找 current_sum - k 是否存在。如果存在，说明找到了若干个满足条件的子数组，将对应的 value 累加到最终结果 ans 中。
  7. 查询完后，将当前的前缀和 current_sum 存入哈希表（或更新其出现次数），供后续的计算使用。
  8. 初始化技巧：为了处理从索引 0 开始的子数组（即 pre[j] 中 j=0 的情况，其前缀和为 0），需要在哈希表中预先放入 (0, 1)，表示和为 0 的前缀和已经出现过 1 次。

---

核心思路（本质）

本题的本质是将 “求解定值子数组和” 的问题，通过 “前缀和” 技巧，转化为一个 “寻找两个前缀和之差为定值” 的问题。这与 “两数之和” 问题的思想非常相似，因此可以利用 哈希表 来高效地进行查找，将时间复杂度从 O(n^2) 优化到 O(n)。

---

总结

（一句话总结触发器）

看到 “连续子数组和”、“定值 k” 且包含负数 → 前缀和 + 哈希表。