🔗 和为 K 的子数组

题目来源：560. 和为 K 的子数组 – 力扣（LeetCode）

---

📌 题目描述

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

• 子数组 是数组中元素的连续非空序列。
• 子数组的和等于 k 即为满足条件。

---

✅ 示例解析

示例 1：

• 输入：nums = [1,1,1], k = 2
• 输出：2
• 解释：和为 2 的子数组有两个：
  • [1,1]（索引 0 到 1）
  • [1,1]（索引 1 到 2）

示例 2：

• 输入：nums = [1,2,3], k = 3
• 输出：2
• 解释：和为 3 的子数组有：
  • [1,2]（索引 0 到 1）
  • [3]（索引 2 到 2）

示例 3：

• 输入：nums = [1,-1,0], k = 0
• 输出：3
• 解释：和为 0 的子数组有 [1,-1]、[0]、[1,-1,0]，共 3 个。

---

⚠️ 提示

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

---

💡 解法：前缀和 + 哈希表（优化暴力）—— O(n) 时间

class Solution {
    public int subarraySum(int[] nums, int k) {
        int sum = 0, ans = 0;
        Map<, Integer> map = new HashMap<>();
        map.put(0, 1);
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (map.containsKey(sum - k)) {
                ans += map.get(sum - k);
            }
            map.put(sum, map.getOrDefault(sum, 0) + 1);
        }
        return ans;
    }
}

---

📊 复杂度分析

• 时间复杂度：O(n)
  仅需一次遍历数组，哈希表的插入与查询操作平均为 O(1)，整体为线性时间。
• 空间复杂度：O(n)
  哈希表最多存储 n+1 个不同的前缀和，因此空间复杂度为 O(n)。

---

🧩 解题思路

1. 前缀和定义：
   设 prefix[i] = nums[0] + nums[1] + ... + nums[i]。
   那么子数组 nums[i..j] 的和为：
   prefix[j] - prefix[i-1]。
2. 目标转换：
   要求 sum(i, j) = k，即：
   prefix[j] - prefix[i-1] = k
   ⇒ prefix[i-1] = prefix[j] - k 因此，对于当前前缀和 prefix[j]，只需查找之前有多少个前缀和等于 prefix[j] - k。
3. 哈希表优化：
   • 使用 Map<Integer, Integer> 记录每个前缀和出现的次数。
   • 遍历过程中：
     • 计算当前前缀和 sum
     • 查询 sum - k 是否存在，若存在则累加其出现次数
     • 将当前 sum 加入哈希表
4. 初始化技巧：
   map.put(0, 1) 表示前缀和为 0 的情况出现了一次（空区间），用于处理从索引 0 开始的子数组。
5. 举例说明：
   对于 nums = [1,1,1], k = 2：
   • i=0: sum=1, 查找 1-2=-1 → 无，map={0:1, 1:1}
   • i=1: sum=2, 查找 2-2=0 → 存在，ans += 1，map={0:1,1:1,2:1}
   • i=2: sum=3, 查找 3-2=1 → 存在，ans += 1，最终 ans=2