Leetcode之523-连续的子数组和(Continuous Subarray Sum)

算法题

题干

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

说明

  1. 数组的长度不会超过10,000。
  2. 你可以认为所有数字总和在 32 位有符号整数范围内。

示例

1
2
3
4
5
6
7
8
9
示例1:
输入: [23,2,4,6,7], k = 6
输出: True
解释: [2,4] 是一个大小为 2 的子数组,并且和为 6。

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

解法

  1. 暴力破解, 双层for循环
  2. 单层循环+HashMap存储

思路

目标: 求解和为k的n倍的连续子数组是否存在
说明: sum[n-m]为数组索引n到m的元素之和, mod_mk为sum[0-m]对k取余的结果
假设: sum[n-m]为目标子数组的和
推导:

  1. sum[n-m] = sum[0-m] - sum[0-n]
  2. sum[0-m] = b*k + mod_mk
  3. sum[0-n] = c*k + mod_nk
  4. sum[n-m] = (b-c)*k + (mod_mk - mod_nk)
  5. 如果想要sum[n-m]可以被k整除, 那么mod_mk-mod_nk必须为0,换句话讲就是sum[0-m]与sum[0-n]对k取余值必须一样
  6. 那么反应到代码里, 我们只需用HashMap记录sum针对k取余的结果以及对应的索引值即可, 看后续的sum值针对k取余的结果在HashMap中是否存在, 如果存在说明中间连续子数组的和就能够被k整除

Java代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean checkSubarraySum(int[] nums, int k) {
if (nums == null || nums.length <= 1) {
return false;
}
Map<Integer, Integer> map = new HashMap<>(16);
map.put(0, -1);
final int LENGTH = nums.length;
int sum = 0;
for (int i = 0; i < LENGTH; i++) {
sum += nums[i];
if (k != 0) {
sum %= k;
}
Integer preIndex = map.get(sum);
if (preIndex != null) {
if (i - preIndex > 1) {
return true;
}
} else {
map.put(sum, i);
}
}
return false;
}

代码解析

  1. 第5行代码新建HashMap, key为sum被k整除之后的余数, value为sum对应的数组索引值
  2. 第6行代码初始化HashMap, 考虑数组前两个元素之和为k的整数倍的case
  3. 第16-18行代码是题干中要求子数组长度至少为2

总结

  1. 注意除数k为0的case
  2. 本身题目不难, 与之前两数之和类似, 都采用HashMap记录, 重点是Map key值到底存什么, value存什么
如果有任何错误或疑问, 欢迎小伙伴们评论区留言^-^
( 完 )

欢迎各位看官关注

麻辣烫,走起
0%