题目

标题和出处

标题：连续的子数组和

出处：523. 连续的子数组和

难度

5 级

题目描述

要求

给定一个整数数组 $\text{nums}$ 和一个整数 $\text{k}$，如果 $\text{nums}$ 有一个连续子数组满足大小至少为 $\text{2}$ 且元素和是 $\text{k}$ 的倍数，则返回 $\text{true}$，否则返回 $\text{false}$。

对于整数 $\text{x}$，如果存在一个整数 $\text{n}$ 使得 $\text{x}=\text{n}\times \text{k}$，则 $\text{x}$ 是 $\text{k}$ 的倍数。$\text{0}$ 总是 $\text{k}$ 的倍数。

示例

示例 1：

输入：$\text{nums = [23,2,4,6,7], k = 6}$
输出：$\text{true}$
解释：$\text{[2, 4]}$ 是大小为 $\text{2}$ 的子数组，和为 $\text{6}$。

示例 2：

输入：$\text{nums = [23,2,6,4,7], k = 6}$
输出：$\text{true}$
解释：$\text{[23, 2, 6, 4, 7]}$ 是大小为 $\text{5}$ 的子数组，和为 $\text{42}$。
$\text{42}$ 是 $\text{6}$ 的倍数，因为 $\text{42}=\text{7}\times \text{6}$ 且 $\text{7}$ 是一个整数。

示例 3：

输入：$\text{nums = [23,2,6,4,7], k = 13}$
输出：$\text{false}$

数据范围

• $\text{1}\le \text{nums.length}\le {\text{10}}^{\text{5}}$
• $\text{0}\le \text{nums[i]}\le {\text{10}}^{\text{9}}$
• $\text{0}\le \text{sum(nums[i])}\le {\text{2}}^{\text{31}}-\text{1}$
• $\text{1}\le \text{k}\le {\text{2}}^{\text{31}}-\text{1}$

解法

思路和算法

只有当数组 $\text{nums}$ 的长度至少为 $2$ 时，才可能存在长度至少为 $2$ 的子数组。如果数组 $\text{nums}$ 的长度小于 $2$，则一定不存在长度至少为 $2$ 的子数组，返回 $\text{false}$。

当数组 $\text{nums}$ 的长度至少为 $2$ 时，为了计算数组 $\text{nums}$ 的子数组的元素和，需要计算数组 $\text{nums}$ 的前缀和，根据前缀和得到任意一个子数组的元素和。

为了判断子数组的元素和是否为 $k$ 的倍数，需要计算前缀和模 $k$ 的余数。对于两个不同的下标 $i$ 和 $j$，其中 $i<j$，如果这两个下标对应的前缀和模 $k$ 的余数相同，则下标范围 $[i+1,j]$ 的子数组的元素和为 $k$ 的倍数，该子数组的长度为 $j-i$。由于这道题要求子数组的长度至少为 $2$，因此应该寻找符合要求的最长子数组，需要记录每个余数的第一次出现的下标。

从左到右遍历数组 $\text{nums}$，遍历过程中计算前缀和模 $k$ 的余数，并使用哈希表记录每个余数的首次出现下标。由于空前缀不包含任何元素，前缀和为 $0$，余数也为 $0$，其下标为 $-1$，因此首先将余数 $0$ 对应下标 $-1$ 存入哈希表。

用 $\text{sum}$ 表示前缀和模 $k$ 的余数，初始时 $\text{sum}=0$。遍历到每个元素时，将该元素值加到 $\text{sum}$，然后将 $\text{sum}$ 的值更新为 $\text{sum}\mathrm{mod}k$（应确保 $0\le \text{sum}<k$）。更新 $\text{sum}$ 的值之后，判断哈希表中是否存在余数 $\text{sum}$，执行相应的操作。

• 如果哈希表中存在余数 $\text{sum}$，则从哈希表中得到 $\text{sum}$ 第一次出现的下标 $\text{prevIndex}$，用 $i$ 表示当前下标，则以当前元素结尾的和为 $k$ 的倍数的最长子数组的长度是 $i-\text{prevIndex}$，如果 $i-\text{prevIndex}\ge 2$，则找到一个长度至少为 $2$ 且和为 $k$ 的倍数的的子数组，返回 $\text{true}$。

• 如果哈希表中不存在余数 $\text{sum}$，则当前下标是余数 $\text{sum}$ 第一次出现，将 $\text{sum}$ 对应下标 $i$ 存入哈希表。

遍历结束之后，如果没有找到长度至少为 $2$ 且和为 $k$ 的倍数的的子数组，则返回 $\text{false}$。

由于哈希表中存储的是每个余数第一次出现的下标，因此当遍历到下标 $i$ 时，如果哈希表中存在相同余数的下标 $\text{prevIndex}$，则以下标 $i$ 结尾的和为 $k$ 的倍数的最长子数组的长度是 $i-\text{prevIndex}$。如果 $i-\text{prevIndex}<2$，则以下标 $i$ 结尾的子数组中不存在长度至少为 $2$ 且和为 $k$ 的倍数的子数组。因此上述做法可以确保得到正确的结果。

代码

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

复杂度分析

• 时间复杂度：$O(n)$，其中 $n$ 是数组 $\text{nums}$ 的长度。需要遍历数组一次计算前缀和模 $k$ 的余数，对于每个元素，更新余数、计算答案与操作哈希表的时间都是 $O(1)$。

• 空间复杂度：$O(k)$，其中 $k$ 是给定的整数。空间复杂度主要取决于哈希表，哈希表中的不同余数个数不超过 $k$ 个。