题目描述

给定一个包含 非负整数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，总和为 k 的倍数，即总和为 n*k，其中 n 也是一个 整数。

样例

输入：[23,2,4,6,7], k = 6
输出：True
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6。

输入：[23,2,6,4,7], k = 6
输出：True
解释：[23,2,6,4,7]是大小为 5 的子数组，并且和为 42。

注意

• 数组的长度不会超过 10000。
• 你可以认为所有数字总和在 32 位有符号整数范围内。

算法

(前缀和，哈希表) $O(n)$

1. 连续子数组的和可以由两个前缀和相减得到。
2. 如果两个前缀和在模 k 下相等，则说明找到了一个连续子数组的和是 k 的倍数。
3. 可以使用哈希表 unordered_set 记录哪些前缀和已经存在。
4. 首先将 0 放入到哈希表中，用来判断某个前缀和模 k 等于 0。
5. 定义两个变量 x 和 y，分别表示从当前位置前一位的前缀和与当前位置的前缀和，这是因为子数组的长度需要至少为 2。
6. 从下标 1 位置开始遍历，遍历时，首先令 y 累加 nums[i]，然后判断 y 是否出现在了哈希表中；如果未出现，则令 x 累加 nums[i - 1]，然后把 x 放入到哈希表中。
7. 注意 k == 0 的特殊情况。

时间复杂度

• 每个数字仅遍历一次，哈希表单次操作复杂度为 $O(1)$，故总时间复杂度为 $O(n)$。

空间复杂度

• 需要额外 $O(n)$ 的空间存储哈希表。

C++ 代码

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        const int n = nums.size();
        if (k == 0) {
            for (int i = 1; i < n; i++)
                if (nums[i] == 0 && nums[i - 1] == 0)
                    return true;
            return false;
        }

        unordered_set<int> seen;
        seen.insert(0);
        int x = 0, y = nums[0];

        for (int i = 1; i < n; i++) {
            y = (y + nums[i]) % k;
            if (seen.find(y) != seen.end())
                return true;

            x = (x + nums[i - 1]) % k;
            seen.insert(x);
        }

        return false;
    }
};