连续的子数组和 图解题解

这道题到底在问什么

输入

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

输出

true （[2,4] 和为 6）

输入

nums=[1,2,12], k=6

输出

false

最优解：一步一步想明白

1. 3记住「前缀和取余，余数重复且间距≥2 即命中；哈希存最早下标」，下面每帧都在套它。
2. 4开局先放一条「余数 0 → 下标 −1」：代表「什么都不取」的空前缀。这样从下标 0 开始的整段也能被正确匹配。
3. 5扫到下标 0（值 2），更新前缀和并对 11 取余，得到余数 2。拿它去哈希表查：之前出现过吗？
4. 6余数 2 是第一次见，把「余数 2 → 最早下标 0」存进哈希表（只存最早的，后面才好凑长间距）。继续下一个。
5. 7扫到下标 1（值 3），更新前缀和并对 11 取余，得到余数 5。拿它去哈希表查：之前出现过吗？
6. 8余数 5 是第一次见，把「余数 5 → 最早下标 1」存进哈希表（只存最早的，后面才好凑长间距）。继续下一个。
7. 9扫到下标 2（值 4），更新前缀和并对 11 取余，得到余数 9。拿它去哈希表查：之前出现过吗？
8. 10余数 9 是第一次见，把「余数 9 → 最早下标 2」存进哈希表（只存最早的，后面才好凑长间距）。继续下一个。
9. 11扫到下标 3（值 5），更新前缀和并对 11 取余，得到余数 3。拿它去哈希表查：之前出现过吗？
10. 12余数 3 是第一次见，把「余数 3 → 最早下标 3」存进哈希表（只存最早的，后面才好凑长间距）。继续下一个。
11. 13扫到下标 4（值 4），更新前缀和并对 11 取余，得到余数 7。拿它去哈希表查：之前出现过吗？
12. 14余数 7 是第一次见，把「余数 7 → 最早下标 4」存进哈希表（只存最早的，后面才好凑长间距）。继续下一个。
13. 15扫到下标 5（值 5），更新前缀和并对 11 取余，得到余数 1。拿它去哈希表查：之前出现过吗？
14. 16余数 1 是第一次见，把「余数 1 → 最早下标 5」存进哈希表（只存最早的，后面才好凑长间距）。继续下一个。
15. 17扫到下标 6（值 7），更新前缀和并对 11 取余，得到余数 8。拿它去哈希表查：之前出现过吗？
16. 18余数 8 是第一次见，把「余数 8 → 最早下标 6」存进哈希表（只存最早的，后面才好凑长间距）。继续下一个。
17. 19扫到下标 7（值 7），更新前缀和并对 11 取余，得到余数 4。拿它去哈希表查：之前出现过吗？
18. 20余数 4 是第一次见，把「余数 4 → 最早下标 7」存进哈希表（只存最早的，后面才好凑长间距）。继续下一个。
19. 21扫到下标 8（值 9），更新前缀和并对 11 取余，得到余数 2。拿它去哈希表查：之前出现过吗？
20. 22余数 2 之前在下标 0 出现过，间距 8 ≥ 2，它们之间这段（绿色）前缀和之差正好是 11 的倍数，找到了！返回 true。
21. 23绿色这段（下标 1..8，3+4+5+4+5+7+7+9 = 44）的和是 11 的倍数，长度 ≥ 2，所以答案 true。本质就是「两处前缀和余数相同」。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

from typing import List
class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        first = {0: -1}
        prefix = 0
        for i, x in enumerate(nums):
            prefix = (prefix + x) % k
            if prefix in first:
                if i - first[prefix] >= 2:
                    return True
            else:
                first[prefix] = i
        return False

#include <unordered_map>
#include <vector>
using namespace std;
class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> first;
        first[0] = -1;
        long long prefix = 0;
        for (int i = 0; i < (int)nums.size(); ++i) {
            prefix = (prefix + nums[i]) % k;
            int r = (int)prefix;
            if (first.count(r)) { if (i - first[r] >= 2) return true; }
            else first[r] = i;
        }
        return false;
    }
};

import java.util.*;
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        Map<Integer,Integer> first = new HashMap<>();
        first.put(0, -1);
        int prefix = 0;
        for (int i = 0; i < nums.length; i++) {
            prefix = (prefix + nums[i]) % k;
            if (first.containsKey(prefix)) { if (i - first.get(prefix) >= 2) return true; }
            else first.put(prefix, i);
        }
        return false;
    }
}

复杂度

面试官可能追问