题目大意：
连续的子数组和
给定一个包含 非负数 的数组和一个目标 整数 k，编写一个函数来判断该数组是否含有连续的子数组，其大小至少为 2，且总和为 k 的倍数，即总和为 n*k，其中 n 也是一个整数。
示例 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。
说明：
- 数组的长度不会超过 10,000 。
- 你可以认为所有数字总和在 32 位有符号整数范围内。
如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=523
解题思路分析：
本题前缀和数组加暴力解是可行的，但本文我们力求最优解，因此，暴力解法简单带过。
解法一：前缀和加暴力遍历每个子数组。
- 先计算出前缀和数组。推导公式如下：
- presum[0]=nums[0]
- presum[i]=presum[i-1]+nums[i] （i>0）
- 两层循环，遍历每一个子数组，当前子数组区间[i,j]和的公式如下。查看该和是否能被k整除
- presum[j] – presum[i] + nums[i]
实现代码：
public class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int[] sum = new int[nums.length];
sum[0] = nums[0];
for (int i = 1; i < nums.length; i++)
sum[i] = sum[i - 1] + nums[i];
for (int start = 0; start < nums.length - 1; start++) {
for (int end = start + 1; end < nums.length; end++) {
int summ = sum[end] - sum[start] + nums[start];
if (summ == k || (k != 0 && summ % k == 0))
return true;
}
}
return false;
}
}解法二：HashMap。O(n)解法
本解法我们依旧需要利用到前缀和数组，但是数组中存的不是和，而是前缀和与k的余数。
试想，如果一个子数组区间[i, j]之和与k的余数为0，也就是说：
(presum[j]-presum[i]+nums[i]) mod k == 0.
我们可将上述公式推导为：
(presum[j]-presum[i-1]) mod k == 0.
进而得到：
presum[j] mod k == presum[i-1] mod k
因此可得出结论，当前缀和数组中出现相同数值时（注意数组中存放的是前缀和与k的余数），我们可以推导出当前存在一个子数组之和可以被k整除。解题时，我们另外使用一个HashMap，记录已经出现过的前缀和（前缀和与k的余数）。另外注意对数字0的处理，详见代码。
实现代码：
public boolean checkSubarraySum(int[] nums, int k) {
int sum = 0;
HashMap <Integer, Integer> map = new HashMap<>();
map.put(0, -1);
for (int i = 0; i < nums.length; 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;
}本题解法执行时间为2ms。
Runtime: 2 ms, faster than 99.79% of Java online submissions for Continuous Subarray Sum.
Memory Usage: 52.7 MB, less than 5.06% of Java online submissions for Continuous Subarray Sum.
本网站文章均为原创内容，并可随意转载，但请标明本文链接如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-523-continuous-subarray-sum-解题思路分析/