0%

LeetCode - 523 - 连续的子数组和

题目

连续的子数组和

题解

官方题解

如果事先计算出数组 nums 的前缀和数组,则对于任意一个子数组,都可以在 O(1) 的时间内得到其元素和。用 prefixSums[i] 表示数组 nums 从下标 00 到下标 i 的前缀和,则 nums 从下标 p+1 到下标 q(其中 p<q)的子数组的长度为 q−p,该子数组的元素和为 prefixSums[q]−prefixSums[p]

如果 prefixSums[q]−prefixSums[p] 为 k 的倍数,且 q−p≥2,则上述子数组即满足大小至少为 2 且元素和为 k 的倍数。

prefixSums[q]−prefixSums[p] 为 k 的倍数时,prefixSums[p]prefixSums[q] 除以 k 的余数相同。因此只需要计算每个下标对应的前缀和除以 k 的余数即可,使用哈希表存储每个余数第一次出现的下标。

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
38
39
40
var checkSubarraySum = function (nums, k) {
const m = nums.length;
if (m < 2) {
return false;
}
const map = new Map();
map.set(0, -1);
let remainder = 0;
for (let i = 0; i < m; i++) {
remainder = (remainder + nums[i]) % k;
if (map.has(remainder)) {
const prevIndex = map.get(remainder);
// 2 - 0 >= 2
if (i - prevIndex >= 2) {
return true;
}
} else {
map.set(remainder, i);
// 5 0
// 1 2
}
}
return false;
};

let nums = [23, 2, 4, 6, 7],
k = 6;

console.log(checkSubarraySum(nums, k));

// 0 23%6
// 5
// 1 7%6
// 1
// 2 5%6
// 5
// 11%6
// 5
// 12%6
// 0

收获

我看到解题方法(上面的加粗划重点)我已经麻了,这是数学规律吗?

prefixSums[q]−prefixSums[p] 为 k 的倍数时,prefixSums[p]prefixSums[q] 除以 k 的余数相同。因此只需要计算每个下标对应的前缀和除以 k 的余数即可,使用哈希表存储每个余数第一次出现的下标。

数组为 [23, 2, 4, 6, 7] k6

prefixSums[q]−prefixSums[p] 为 k 的倍数

1
((23 + 2 + 4) - 23) % 6 = 0

只要下面这两个余数相同就可以了

1
2
23 % 6 = 5
(23 + 2 + 4) % 6 = 5