来自Leetcode第560题和为K的子数组
给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。
示例 1 :
1
2
| 输入:nums = , k = 2
输出: 2 , 与 为两种不同的情况。
|
暴力遍历
$O(n^2)$，但是要考虑负数的情况，因而不能当$result > k$时就跳出循环。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
| class Solution {
public int subarraySum(int[] nums, int k) {
int count = 0;
for(int i = 0;i < nums.length;i++){
int result = 0;
for(int j = i;j < nums.length;j++){
result += nums[j];
if(result == k){
count++;
}
}
}
return count;
}
}
|
前缀和
定义$pre[i]$为数组$[0..i]$里所有数的和，则有$pre[i] = pre[i-1] + nums[i]$
进而$[j…i]这个子数组的和为k$可以转化为$pre[i] - pre[j-1] == k $
进而有$pre[j-1] == pre[i]-k$
所以考虑以$i$结尾的和为$k$的连续子数组需要统计前缀和为$pre[i]-k 的 pre[j]$的出现次数。可以考虑用一个HashMap存储前缀和以及对应的出现次数，从左往右遍历一遍即可。
1
2
3
4
5
6
7
8
9
10
11
12
13
| public int subarraySum(int[] nums ,int k){
int cnt = 0 ,preSum = 0;
HashMap<Integer,Integer> map = new HashMap<>();
map.put(0,1);
for(int i = 0 ; i < nums.length ; ++i){
preSum += nums[i];
if(map.containsKey(preSum -k)){
cnt += map.get(preSum - k);
}
map.put(preSum,map.getOrDefault(preSum,0)+1);
}
return cnt;
}
|
前缀和优化
将$nums[i]$当作从$[0…i]$里所有数的前缀和，记录前缀和里的最大值最小值max,min,这样开始数组做HashMap时只需要$max - min + 1$大小的空间。
接下来就是对前缀和遍历，如果前缀和$nums[i]==k$，对应的计数就加一，如果$nums[i]-k>=min \&\& nums[i]-k<=max$说明$map[nums[i] - k - min]$也是满足上文中提到的$pre[j-1] == pre[i]-k$的例子，之所以要满足$nums[i]-k>=min \&\& nums[i]-k<=max$是为了避免越界。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| public int subarraySum(int[] nums, int k) {
if(nums.length==0) return 0;
int max=nums[0];
int min=nums[0];
for(int i=1;i<nums.length;i++){
nums[i]+=nums[i-1];
max=max>nums[i]?max:nums[i];
min=min<nums[i]?min:nums[i];
}
int count=0;
int map[]=new int[max-min+1];
for(int i=0;i<nums.length;i++){
if(nums[i]==k){
count++;
}
if(nums[i]-k>=min&&nums[i]-k<=max){
count+=map[nums[i]-k-min];
}
map[nums[i]-min]++;
}
return count;
}
|