LeetCode 523. Continuous Subarray Sum

题目链接 Continuous Subarray Sum

相关题目blog地址

Subarray Sum Equals K

Maximum Product Subarray

Subarray Product Less Than K



题意很简单,给定一个非负数序列和一个数字 k,求解有多少个连续的长度至少为2的子数组使得子数组的和是 k 的整倍数,这题主要是有些 corner case 要考虑清楚, 思路跟 LeetCode 560类似,不过这题比那题要稍微难一些.思路就是用一个 hashmap 保存遍历的当前累计和,然后检查累积和是 k 的多少倍(m 倍),然后检查从 m,m-1,m-2….1倍有没有可能成立.检查方式是查看 hashmap 里有没有sum - beishu * k,看代码吧..我语文有点捉鸡

this is my code

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
26
27
28
29
30
31
32
33
34
35
36
37
public static boolean checkSubarraySum(int[] nums, int k) {
if (k < 0) {
k = -k;
}
if (k == 0) {
for (int i = 1; i < nums.length; i++) {
if (nums[i] == nums[i - 1] && nums[i] == 0) {
return true;
}
}
return false;
}
if (nums.length == 1) return false;
Map<Integer, Integer> map = new HashMap<>();
map.put(nums[0], 0);
int sum = nums[0];
for (int i = 1; i < nums.length; i++) {
if (nums[i] == 0 && nums[i - 1] == 0) {
return true;
}
sum += nums[i];
int target = sum % k;
if (target == 0) {
return true;
} else {
int beishu = sum / k;
for (; beishu >= 1; beishu--) {
if (map.containsKey(sum - beishu * k) && i - map.get(sum - beishu * k) > 0) {
return true;
}
}
}

map.put(sum, i);
}
return false;
}
月月说要给我打赏,就还是放了二维码,😝