# LEETCODE 523. Continuous Subarray Sum 解题思路分析

```输入：[23,2,4,6,7], k = 6

```输入：[23,2,6,4,7], k = 6

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

1. 先计算出前缀和数组。推导公式如下：
• presum[0]=nums[0]
• presum[i]=presum[i-1]+nums[i] （i>0）
2. 两层循环，遍历每一个子数组，当前子数组区间[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;
}
}```

`(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`

```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;
}```

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.