# 「力扣」第 523 题：连续的子数组（中等）
说明：题解里有些内容（图片）来自官方题解，以前在「力扣」上班维护过。
# 题目描述
给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：
- 子数组大小 至少为 2 ，且
- 子数组元素总和为
k的倍数。
如果存在，返回 true ；否则，返回 false 。
如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。0 始终视为 k 的一个倍数。
示例 1：
输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。
示例 2：
输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。
示例 3：
输入：nums = [23,2,6,4,7], k = 13
输出：false
提示：
1 <= nums.length <= 10^50 <= nums[i] <= 10^9
# 思路分析
说明：本题解修改自原始的官方题解，现在的官方题解已经被官方题解团队修改过。
概述：
- 这道问题我们使用三种方法，层层递进介绍了这个问题的解法，基本的思路是 空间换时间；
- 如果空间使用恰当，可以减少遍历的次数；
- 这道问题的方法二和方法三都很有代表性，大家需要仔细体会。
# 方法一：暴力解法（超时）
考虑所有长度 大于等于
参考代码 1：
public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int len = nums.length;
for (int left = 0; left < len - 1; left++) {
for (int right = left + 1; right < len; right++) {
int sum = 0;
for (int i = left; i <= right; i++) {
sum += nums[i];
}
if (sum == k || (k != 0 && sum % k == 0)) {
return true;
}
}
}
return false;
}
}
复杂度分析：
- 时间复杂度：
。三重嵌套的 for循环遍历数组； - 空间复杂度：
，只用了常数个额外变量。
# 方法二：前缀和（超时）
基本思想：空间换时间。
- 注意到题目中我们求连续子数组的区间和；
- 求区间和的一个基本的技巧是：根据前缀和的差，求出区间和。
参考代码 2：
public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int len = nums.length;
// preSum[i] 表示：区间 [0..i) 的前缀和
int[] preSum = new int[len + 1];
preSum[0] = 0;
for (int i = 0; i < len; i++) {
preSum[i + 1] = preSum[i] + nums[i];
}
for (int left = 0; left < len - 1; left++) {
for (int right = left + 1; right < len; right++) {
int sum = preSum[right + 1] - preSum[left];
if (sum == k || (k != 0 && sum % k == 0)) {
return true;
}
}
}
return false;
}
}
复杂度分析
- 时间复杂度：
。为了考虑每一个子数组，我们需要一个 2 重嵌套的循环。 - 空间复杂度：
。 使用了长度为 的 数组。
事实上，当前问题是一个计数问题，根据求解 1. 两数之和 的经验，我们可以在遍历的过程当中记录已经出现的信息，这样就可以通过一次遍历完成计算。已经遍历过的信息就需要记录下来，我们使用 哈希表。
# 方法三：前缀与哈希表
使用哈希表保存到下标
原因如下：遍历输入数组，记录到当前位置为止的 sum % k，value：i。
假设第
基于这一观察，可以得出结论：
无论何时，只要
下面的幻灯片描述了数组 nums = [2, 5, 33, 6, 7, 25, 15] 且 k = 13 的求解过程。
import java.util.HashMap;
import java.util.Map;
public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int sum = 0;
// key：区间 [0..i] 里所有元素的和 % k
// value：下标 i
Map<Integer, Integer> map = new HashMap<>();
// 理解初始化的意义
map.put(0, -1);
int len = nums.length;
for (int i = 0; i < len; i++) {
sum += nums[i];
if (k != 0) {
sum = sum % k;
}
if (map.containsKey(sum)) {
if (i - map.get(sum) > 1) {
return true;
}
} else {
map.put(sum, i);
}
}
return false;
}
}
复杂度分析
- 时间复杂度：
，仅需要遍历输入数组一遍； - 空间复杂度：
。哈希表最多包含 个不同的元素。
作者：liweiwei1419 链接：https://suanfa8.com/prefix-sum/solutions-1/0523-continuous-subarray-sum 来源：算法吧 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。