523. 连续的子数组和
题目描述
输入整数数组 nums 和整数 k。
判断 nums 中是否存在一段连续的子数组，同时满足两点：长度不少于 2；元素之和是 k 的整数倍。这里 0 也算作 k 的倍数。
存在则返回 true，否则返回 false。
示例 1
输入：nums = [23,2,4,6,7], k = 6 输出：true
解释：[2,4] 的和为 6，是 6 的倍数。
示例 2
输入：nums = [23,2,6,4,7], k = 6 输出：true
解释：整个数组的和为 42，等于 7 * 6。
示例 3
输入：nums = [23,2,6,4,7], k = 13 输出：false
解释：找不到长度至少为 2 且和为 13 的倍数的连续段。
数据范围
1 <= nums.length <= 10^50 <= nums[i] <= 10^90 <= sum(nums[i]) <= 2^31 - 11 <= k <= 2^31 - 1
解题思路
子数组 nums[j+1..i] 的和等于前缀和之差 P[i] - P[j]。它是 k 的倍数，当且仅当 P[i] 和 P[j] 除以 k 的余数相同。所以用哈希表记录每个余数第一次出现的下标（空前缀的余数 0 记在下标 -1）。再次遇到同一余数时，只要距离至少 2 就找到了。只保留最早的下标，是为了让子数组尽可能长。
为什么正确
first[r] 是已扫描前缀中余数为 r 的最小下标；若当前余数 s 已在表中，则以 i 结尾的最长合法子数组是 nums[first[s]+1..i]。
复杂度分析
时间 O(n)，空间 O(min(n, k))。
易错点
忘记放入 {0: -1}，会漏掉从下标 0 开始的子数组；遇到重复余数时用新下标覆盖旧下标，会让 [5,0,0] 这类数据在 k 任意时错失长度为 2 的解。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
first = {0: -1}
s = 0
for i, x in enumerate(nums):
s = (s + x) % k
if s in first:
if i - first[s] >= 2:
return True
else:
first[s] = i
return Falseclass Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Long, Integer> first = new HashMap<>();
first.put(0L, -1);
long s = 0;
for (int i = 0; i < nums.length; i++) {
s = (s + nums[i]) % k;
if (first.containsKey(s)) {
if (i - first.get(s) >= 2) {
return true;
}
} else {
first.put(s, i);
}
}
return false;
}
}class Solution {
public:
bool checkSubarraySum(vector<int>& nums, int k) {
unordered_map<long long, int> first;
first[0] = -1;
long long s = 0;
for (int i = 0; i < (int)nums.size(); i++) {
s = (s + nums[i]) % k;
if (first.count(s)) {
if (i - first[s] >= 2) {
return true;
}
} else {
first[s] = i;
}
}
return false;
}
};func checkSubarraySum(nums []int, k int) bool {
first := map[int]int{0: -1}
s := 0
for i, x := range nums {
s = (s + x) % k
if j, ok := first[s]; ok {
if i-j >= 2 {
return true
}
} else {
first[s] = i
}
}
return false
}var checkSubarraySum = function(nums, k) {
const first = new Map([[0, -1]]);
let s = 0;
for (let i = 0; i < nums.length; i++) {
s = (s + nums[i]) % k;
if (first.has(s)) {
if (i - first.get(s) >= 2) {
return true;
}
} else {
first.set(s, i);
}
}
return false;
};function checkSubarraySum(nums: number[], k: number): boolean {
const first = new Map<number, number>([[0, -1]]);
let s = 0;
for (let i = 0; i < nums.length; i++) {
s = (s + nums[i]) % k;
if (first.has(s)) {
if (i - first.get(s)! >= 2) {
return true;
}
} else {
first.set(s, i);
}
}
return false;
}