【LeetCode 热题 100】（四）子串

560. 和为k的子数组

class Solution {
    public int subarraySum(int[] nums, int k) {
        // 1.定义全局总个数
        int count = 0;
        int pre = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        map.put(0,1);
        for (int i = 0; i < nums.length; i++) {
            pre = pre + nums[i];
            if(map.containsKey(pre - k)){
                count = count + map.get(pre-k);
            }
            map.put(pre, map.getOrDefault(pre,0) + 1);
        }
        return count;
    }
}

解题思路：前缀和 + 哈希表（统计和为K的子数组数量）

核心思想

使用前缀和技巧配合哈希表高效统计连续子数组的和等于目标值 k 的数量，避免暴力解法的O(n²)时间复杂度。

关键概念

1. 前缀和 pre：

   • 表示从数组起始位置到当前位置的所有元素之和
   • pre = nums[0] + nums[1] + ... + nums[i]

2. 子数组和与k的关系：

   • 子数组 [j, i] 的和 = pre[i] - pre[j-1]
   • 当子数组和等于 k 时：pre[i] - pre[j-1] = k
   • 变形为：pre[j-1] = pre[i] - k

算法步骤

1. 初始化：

   int count = 0;          // 统计满足条件的子数组数量
   int pre = 0;            // 当前前缀和（初始为0）
   HashMap<Integer, Integer> map = new HashMap<>();
   map.put(0, 1);          // 关键：前缀和为0的情况出现1次（空数组）
   

2. 遍历数组：

   for (int i = 0; i < nums.length; i++) {
       // 更新前缀和
       pre += nums[i];
       
       // 检查是否存在 pre_j = pre - k
       if (map.containsKey(pre - k)) {
           count += map.get(pre - k);  // 累加符合条件的子数组数量
       }
       
       // 记录当前前缀和出现次数
       map.put(pre, map.getOrDefault(pre, 0) + 1);
   }
   

执行流程（以 nums=[1,1,1], k=2 为例）

关键点解析

1. 为什么需要 map.put(0,1)：

   • 处理子数组从索引0开始的情况
   • 当 pre == k 时，pre-k=0 能在map中找到

2. 哈希表的作用：

   • key：前缀和的值
   • value：该前缀和出现的次数
   • 通过 pre-k 快速查找符合条件的子数组起点数量

3. 时间复杂度 O(n)：

   • 只需遍历数组一次
   • 哈希表操作O(1)时间复杂度

示例说明

• 输入：nums = [1,1,1], k=2
• 有效子数组：
  1. [1,1]（索引0-1）：1+1=2
  2. [1,1]（索引1-2）：1+1=2
• 输出：count = 2

算法优势

1. 高效：相比暴力解法（O(n²)），优化到O(n)
2. 通用：处理正负数混合数组（哈希表不依赖元素顺序）
3. 简洁：仅需单次遍历+常数空间（哈希表大小与数据规模无关）

扩展应用

此方法可解决类似问题：

• 统计子数组和等于k的最小长度
• 寻找和为k的最长子数组
• 处理乘积等其他运算的变种问题