- 2.25
- 用 map 记录前缀和和其次数，不需要手动添加，在 for 中循环边判断边加入
class Solution {
public int subarraySum(int[] nums, int k) {
int res = 0;
int preSum=0;
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
for(int i=0;i<nums.length;i++){
int num = nums[i];
preSum+=num;
if(map.containsKey(preSum-k)){
res+=map.get(preSum-k);
}
map.put(preSum,map.getOrDefault(preSum,0)+1);
}
return res;
}
}-
2.6
- 找 preSum-k，返回 count
-
1.23
- 前缀和，数学问题，找 preSum-k（key），次数（value）
-
11.18
- 中上难度，像 map 里记录的是 presum 当前的前缀和，我们想得到的哪个前缀和只是作为判断条件，来记录 count 值
- 不管怎样，都需记录当前 presum 的前缀和，需要用到 put（x，getorDefualt（））
- 不管怎样，需要初始化第一个情况，前缀和为 0 的出现了一次。
1. 直观比喻：剪绳子
假设你手头有一根很长的绳子（数组），你一直往右走，每走一步就记录一下**“从头开始到现在”的总长度**（这就是 preSum）。
-
现在的任务：你想从这根长绳子里，剪出一段长度正好为 k 的绳子。
-
你当前的位置：假设你现在走到了
10米处（当前preSum= 10）。 -
目标：你要剪一段
k = 3米的绳子，并且这段绳子的终点就是你脚下。
问题来了：这一剪刀应该剪在哪里？
答案：显然是 10 - 3 = 7 米处。
只要之前的记录里，你曾经在 7 米处做过记号（即 Map 里存过 preSum 为 7 的记录），那就说明从那个记号点到你脚下，正好有一段长度为 3 的绳子。
2. 数学推导（公式化理解）
设 preSum[i] 为数组 nums[0] 加到 nums[i] 的和。
如果你想要一段子数组 nums[j...i] 的和等于 k：
$$nums[j] + \dots + nums[i] = k$$
这段子数组的和，其实可以用两个前缀和相减得到：
$$preSum[i] - preSum[j-1] = k$$
-
preSum[i]：从头加到现在的和（当前的长度）。 -
preSum[j-1]：想要去掉的前面的那一截和（需要剪掉的历史长度）。
我们把公式移项一下，就变成了代码里的逻辑：
$$preSum[j-1] = preSum[i] - k$$
翻译成人话：
“我现在手里的总和是 preSum，我想知道有没有一段子数组和是 k。我就回头看一看，历史上（Map里）有没有出现过一个前缀和等于 preSum - k。如果有，把他减掉，剩下的就是 k 了。”
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int count = 0;
int preSum = 0;
for(int num:nums){
preSum+=num;
//如果有前缀和为preSum-k,说明存在一段子数组和为k
if(map.containsKey(preSum-k)){
count+=map.get(preSum-k);//这里需要找到所有map中v值=preSum-k的数量
}
//记录当前前缀和出现次数
//如果map中原来有1=2,经过map.put(1, 3)后会覆盖为1=3
map.put(preSum,map.getOrDefault(preSum,0)+1);
}
return count;
}
}