前缀和
# 560. 和为 K 的子数组 (opens new window)
map记录前缀和元素出现的次数，初始(0,1)；
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0,1);
int preSum = 0;
int ans = 0;
for(int num:nums){
preSum += num;
if(map.containsKey(preSum-k)){
// 1，-1，1，-1 k=0
ans += map.get(preSum-k);
}
map.put(preSum,map.getOrDefault(preSum,0)+1);
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 523. 连续的子数组和 (opens new window)
map记录前缀和和索引，初始(0,0)；
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
map.put(0,0);
int preSum = 0;
for(int i=1;i<=nums.length;i++){
preSum += nums[i-1];
int x = preSum % k;
// if(map.containsKey(x) && (i-map.get(x))>1){
// return true;
// }
// map.put(x,i);
// 0始终视为k的一个倍数
if(!map.containsKey(x)){
map.put(x,i);
}else{
if(i-map.get(x)>1){
return true;
}
}
}
return false;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
# 525. 连续数组 (opens new window)
技巧：0前缀和计算时作为-1；
map存放前缀和与索引，如果不存在key，默认-1；
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer,Integer> map = new HashMap<>();
int n = nums.length;
int[] preSum = new int[n+1];
for(int i=1;i<=n;i++){
preSum[i] = preSum[i-1] + (nums[i-1]==0?-1:1);
}
int ans = 0;
for(int i=0;i<=n;i++){
int j = map.getOrDefault(preSum[i],-1);
if(j<0){
map.put(preSum[i],i);
}else if(i-j>ans){
ans = i-j;
}
}
return ans;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20