523. Continuous Subarray Sum
Given a list of non-negative numbers and a target integer k, write a function to check if the array has a continuous subarray of size at least 2 that sums up to a multiple of k, that is, sums up to n*k where n is also an integer.
Example 1
Input: [23, 2, 4, 6, 7], k=6
Output: True
Explanation: Because [2, 4] is a continuous subarray of size 2 and sums up to 6.
Example 2
Input: [23, 2, 6, 4, 7], k=6
Output: True
Explanation: Because [23, 2, 6, 4, 7] is an continuous subarray of size 5 and sums up to 42.
题意：题意就是给一个数组，问存在不存在一个长度至少为 2 的 subarray 的和为 k 的倍数.
解法 1 最直观的解法就是存两个前缀和数组， 然后遍历所有可能的情况。 这样做的复杂度是 O(n^2) 代码
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;
}
}
解法 2 这个解法是建立上面的解法之上，如果两个数 mod k 余数相同的话，那么两个数之差就是 k 的倍数。简单证明如下， 如果 a 和 b 模 k 余数都是 c 的话，我们可以写成这个表达式 a = xk + c, b = yk + c. 那么 a - b = (x-y) * k. 那么 a 和 b 之差就是 k 的倍数。 借助这个原理， 我们就可以用 map 把前 i 项和模 k 的余数存在 map 里， 这样一旦我们发现有相同的余数，判断一下下标，即可返回。 注意我们要特殊处理 0 的情况。 并且需要把预处理一下。 因为 sum[j] - sum[i] 是 i + 1 到 j 之和。 所以我们要 push 一个 (0, 1) 到 map 中。
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
int sum = 0;
map.put(0, -1);
for(int i = 0; i < nums.length; i++) {
sum += nums[i];
sum = sum % (k == 0 ? sum + 1 : k);
if(map.containsKey(sum)) {
if(i - map.get(sum) > 1) return true;
} else {
map.put(sum, i);
}
}
return false;
}
}