知序
返回
保存草稿
发布
H1
H2
H3
1
2
3
Excalidraw 图
AI 写作
AI 优化
目录
输入内容后显示目录
Markdown
# 82 - 和为K的子数组 ## 题目(LeetCode 560) 给定整数数组和整数 k,找到数组中和为 k 的连续子数组的个数。 ## 解法:前缀和 + 哈希表 ```java class Solution { public int subarraySum(int[] nums, int k) { Map<Integer, Integer> map = new HashMap<>(); map.put(0, 1); int sum = 0, count = 0; for (int num : nums) { sum += num; count += map.getOrDefault(sum - k, 0); map.merge(sum, 1, Integer::sum); } return count; } } ``` ## 复杂度 - 时间 O(n),空间 O(n) ## 一句话总结 前缀和 preSum[i] - preSum[j] = k 等价于找之前出现过的前缀和为 sum - k 的次数。 > 💬 **Q:给出详细解释** > > **核心思路:前缀和的数学变形** > > 子数组 `[j+1, i]` 的和 = `preSum[i] - preSum[j]` > > 要找和等于 k 的子数组,就是找满足 `preSum[i] - preSum[j] = k` 的下标对,变形得 `preSum[j] = preSum[i] - k`。 > > 所以遍历到 i 时,只需查"之前有没有出现过值为 `sum - k` 的前缀和,出现了几次",有几次就说明有几条以 i 结尾的子数组和为 k。 > > **逐行解释代码**: > > ```java > map.put(0, 1); // 初始化:前缀和为 0 出现过 1 次(空前缀,处理从头开始的子数组) > int sum = 0, count = 0; > for (int num : nums) { > sum += num; // sum = preSum[i] > count += map.getOrDefault(sum - k, 0); // 查有多少个 j 满足 preSum[j] = sum-k > map.merge(sum, 1, Integer::sum); // 记录当前前缀和出现一次(等价于 map.put(sum, map.getOrDefault(sum,0)+1)) > } > ``` > > **手动模拟**:`nums = [1, 1, 1]`,k = 2 > > ``` > 初始 map = {0:1},sum = 0 > > i=0: sum=1, 查 1-2=-1 → 无, count=0; map={0:1, 1:1} > i=1: sum=2, 查 2-2=0 → 1次, count=1; map={0:1, 1:1, 2:1} > i=2: sum=3, 查 3-2=1 → 1次, count=2; map={0:1, 1:1, 2:1, 3:1} > > 返回 2,即子数组 [0,1] 和 [1,2] ✓ > ``` > > **为什么初始化 `map.put(0, 1)`?** > > 处理从头开始(j=0)的子数组。如果整段 `nums[0..i]` 的和就等于 k,那么 `sum - k = 0`,查 map 时需要能查到 0 出现过 1 次。否则这种情况会漏掉。 > > **为什么先查再更新 map?** > > 保证查到的都是"当前位置之前"的前缀和,不会把当前的 `sum` 自己算进去(子数组不能长度为 0)。
预览
发布文章
添加摘要让读者更快了解文章内容
取消
确认发布
AI 写作助手
输入一个主题,AI 将为你生成一篇 Markdown 博客文章
AI 正在写作中...
取消
开始生成
AI 优化助手
描述你的修改需求,AI 将在原文基础上进行补充或微调
AI 正在优化中...
取消
开始优化
画布
从已有图里选
✕
图名
保存后生成 /images/excalidraw/<图名>.svg(只能用字母、数字、短横线、下划线、点)
取消
保存并插入