【LeetCode-HOT100】和为K的子数组——前缀和+哈希表详解

一、题目描述LeetCode 560. 和为K的子数组难度⭐⭐⭐ 中等给你一个整数数组nums和一个整数k请你统计并返回该数组中和为k的连续子数组的个数。示例 1text输入nums [1,1,1], k 2 输出2 解释[1,1] 有两个索引0-1和1-2示例 2text输入nums [1,2,3], k 3 输出2 解释[1,2] 和 [3] 两个子数组示例 3text输入nums [1,-1,0], k 0 输出3 解释[1,-1]、[-1,0]、[1,-1,0] 都是0二、解题思路⚠️ 重要提示滑动窗口不适用于此题原因滑动窗口要求窗口具有单调性扩大窗口和一定增加/减少当数组包含负数或0时窗口和不再单调此题最优解是前缀和 哈希表核心思想前缀和公式text子数组和 prefixSum[j] - prefixSum[i-1] k prefixSum[i-1] prefixSum[j] - k遍历数组时计算当前位置的前缀和查找有多少个之前的前缀和等于当前前缀和 - k这些前缀和对应的位置到当前位置的子数组和都为k三、多种解法详解解法一前缀和 哈希表最优解javaclass Solution { public int subarraySum(int[] nums, int k) { // key: 前缀和, value: 该前缀和出现的次数 MapInteger, Integer prefixSumMap new HashMap(); // 初始化前缀和为0出现1次处理从0开始的子数组 prefixSumMap.put(0, 1); int prefixSum 0; int count 0; for (int num : nums) { // 计算当前前缀和 prefixSum num; // 查找是否存在前缀和 prefixSum - k // 如果存在说明这些位置到当前位置的子数组和为k if (prefixSumMap.containsKey(prefixSum - k)) { count prefixSumMap.get(prefixSum - k); } // 将当前前缀和加入哈希表 prefixSumMap.put(prefixSum, prefixSumMap.getOrDefault(prefixSum, 0) 1); } return count; } }图解示例nums [1,2,3], k 3索引num前缀和prefixSum - k存在次数count哈希表状态初始-0--0{0:1}011-200{0:1, 1:1}12301次1{0:1, 1:1, 3:1}23631次2{0:1, 1:1, 3:1, 6:1}结果2解法二暴力枚举不推荐javaclass Solution { public int subarraySum(int[] nums, int k) { int count 0; for (int i 0; i nums.length; i) { int sum 0; for (int j i; j nums.length; j) { sum nums[j]; if (sum k) { count; } } } return count; } }时间复杂度O(n²)大数据量会超时解法三前缀和数组空间换时间javaclass Solution { public int subarraySum(int[] nums, int k) { int n nums.length; int[] prefixSum new int[n 1]; // 计算前缀和数组 for (int i 0; i n; i) { prefixSum[i 1] prefixSum[i] nums[i]; } int count 0; // 枚举所有子数组 for (int i 0; i n; i) { for (int j i 1; j n; j) { if (prefixSum[j] - prefixSum[i] k) { count; } } } return count; } }时间复杂度O(n²)空间复杂度O(n)四、图解示例详解示例1nums [1,1,1], k 2text步骤详解 前缀和0出现1次map {0:1} 索引0num1 prefixSum 1 查找 prefixSum - k -1不存在 map {0:1, 1:1} 索引1num1 prefixSum 2 查找 prefixSum - k 0存在1次 → count 1 map {0:1, 1:1, 2:1} 索引2num1 prefixSum 3 查找 prefixSum - k 1存在1次 → count 1 map {0:1, 1:1, 2:1, 3:1} 最终count 2示例2包含负数的情况textnums [1,-1,0], k 0 初始map {0:1}, prefixSum0, count0 索引0: num1 prefixSum1 查找1-01不存在 map {0:1, 1:1} 索引1: num-1 prefixSum0 查找0-00存在1次 → count1 map {0:2, 1:1} (0的出现次数1) 索引2: num0 prefixSum0 查找0-00存在2次 → count3 map {0:3, 1:1} 最终count 3五、解法对比解法时间复杂度空间复杂度优点缺点前缀和哈希表O(n)O(n)最优一次遍历需要理解前缀和思想暴力枚举O(n²)O(1)简单直观大数据量超时前缀和数组O(n²)O(n)易于理解时间复杂度过高六、关键点解析1. 为什么要初始化 map.put(0, 1)javaprefixSumMap.put(0, 1); // 非常重要原因处理从数组开头开始的子数组text示例nums [3], k 3 前缀和 3 查找 prefixSum - k 0存在1次 → count 1 ✅ 如果不初始化0 查找0不存在 → count 0 ❌2. 为什么不能用滑动窗口java// 错误示例试图用滑动窗口 public int subarraySum(int[] nums, int k) { int left 0, sum 0, count 0; for (int right 0; right nums.length; right) { sum nums[right]; while (sum k left right) { // 有负数时不能这样 sum - nums[left]; left; } if (sum k) count; } return count; }问题当有负数时窗口和可能不增反降sum k的收缩条件失效例如[1,-1,0], k0窗口和会在0、1之间变化3. 哈希表存储的是什么text前缀和 → 出现次数 不是存储索引而是存储出现次数 这样能处理多个相同前缀和的情况七、常见错误与避坑指南错误1忘记初始化0java// ❌ 错误 MapInteger, Integer map new HashMap(); // 没有 put(0,1) // ✅ 正确 MapInteger, Integer map new HashMap(); map.put(0, 1);错误2先put再查找java// ❌ 错误顺序反了 for (int num : nums) { prefixSum num; map.put(prefixSum, map.getOrDefault(prefixSum, 0) 1); // 先put if (map.containsKey(prefixSum - k)) { // 后查找 count map.get(prefixSum - k); } } // ✅ 正确先查找再put for (int num : nums) { prefixSum num; if (map.containsKey(prefixSum - k)) { count map.get(prefixSum - k); } map.put(prefixSum, map.getOrDefault(prefixSum, 0) 1); }原因避免使用当前前缀和自己配对子数组长度至少为1错误3使用int数组当哈希表java// ❌ 错误前缀和可能为负数不能用数组 int[] map new int[1000000]; // 索引不能为负 // ✅ 正确使用HashMap MapInteger, Integer map new HashMap();八、扩展与变体变体1和为K的子数组返回所有子数组javapublic Listint[] subarraySumWithIndices(int[] nums, int k) { Listint[] result new ArrayList(); MapInteger, ListInteger prefixSumMap new HashMap(); prefixSumMap.put(0, new ArrayList()); prefixSumMap.get(0).add(-1); // 虚拟索引 int prefixSum 0; for (int i 0; i nums.length; i) { prefixSum nums[i]; if (prefixSumMap.containsKey(prefixSum - k)) { for (int start : prefixSumMap.get(prefixSum - k)) { result.add(new int[]{start 1, i}); } } prefixSumMap.computeIfAbsent(prefixSum, key - new ArrayList()).add(i); } return result; }变体2和为K的最长子数组长度javapublic int maxSubArrayLen(int[] nums, int k) { MapInteger, Integer prefixSumMap new HashMap(); prefixSumMap.put(0, -1); // 存储第一次出现的位置 int prefixSum 0; int maxLen 0; for (int i 0; i nums.length; i) { prefixSum nums[i]; if (prefixSumMap.containsKey(prefixSum - k)) { maxLen Math.max(maxLen, i - prefixSumMap.get(prefixSum - k)); } // 只存储第一次出现的位置为了最长子数组 prefixSumMap.putIfAbsent(prefixSum, i); } return maxLen; }变体3连续子数组的乘积为K含正数java// 注意乘积问题要考虑0和负数更复杂 public int subarrayProduct(int[] nums, int k) { if (k 1) return 0; int count 0, product 1, left 0; for (int right 0; right nums.length; right) { product * nums[right]; while (product k left right) { product / nums[left]; left; } count right - left 1; } return count; }九、相关题目推荐题目难度核心思路区别[LeetCode 560] 和为K的子数组中等前缀和哈希表统计个数[LeetCode 325] 和为K的最长子数组中等前缀和哈希表最长长度[LeetCode 523] 连续的子数组和中等前缀和哈希表是否为k的倍数[LeetCode 974] 和可被K整除的子数组中等前缀和哈希表同余定理[LeetCode 1] 两数之和简单哈希表非连续十、总结核心要点识别问题类型连续子数组 和 k → 前缀和哈希表数组包含负数/0 → 不能用滑动窗口统计个数 → 哈希表存次数求最长长度 → 哈希表存第一次出现索引公式记忆textprefixSum[j] - prefixSum[i-1] k prefixSum[i-1] prefixSum[j] - k初始化关键javamap.put(0, 1); // 处理从头开始的子数组顺序重要java先查找再put // 避免自己配对自己解题模板javapublic int subarraySum(int[] nums, int k) { MapInteger, Integer map new HashMap(); map.put(0, 1); // 初始化 int prefixSum 0; int count 0; for (int num : nums) { prefixSum num; // 查找之前的前缀和 if (map.containsKey(prefixSum - k)) { count map.get(prefixSum - k); } // 记录当前前缀和 map.put(prefixSum, map.getOrDefault(prefixSum, 0) 1); } return count; }面试技巧先说暴力法O(n²)枚举所有子数组再优化到O(n)引出前缀和思想处理边界k0的情况数组有负数从头开始的子数组复杂度分析时间O(n)空间O(n)十一、参考资料题目链接LeetCode 560. 和为K的子数组官方题解LeetCode 官方题解前缀和详解前缀和算法专题