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 the 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.
Note:
- The length of the array won't exceed 10,000.
- You may assume the sum of all the numbers is in the range of a signed 32-bit integer.
Idea 1: Brute force Compute the sum of each subarray for a given pair of interger 0 <= i <= j-1 <= nums.length-1. The size of the subarray is at least 2, j - i + 1 >= 2, that is j - i >= 1. Check sum[i..j]%k == 0 if k != 0
Note that k could be 0, sum[i..j] = 0
Time complexity: O(n2)
Space complexity: O(1)
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
for(int i = 0; i < nums.length; ++i) {
int sum = 0;
for(int j = i; j < nums.length; ++j) {
sum += nums[j];
if( k == 0 ) {
if(sum == 0 && (j - i >= 1)){
return true;
}
}
else if(sum%k == 0 && j-i >= 1) {
return true;
}
}
}
return false;
}
}
Idea 2: If the remainder of the cumulative sum cumuSum[0...j] ( = k * x + mod1) is equal to that of cumuSum[0...i] ( = k * y + mod2), it means the subarray sum between i and j is a multiple of k, since cumuSum[j] - cumuSum[i] = (x - y) * k.
Note that k could be 0, this case needs to deal differently, cumuSum[j] - cumuSum[i] == 0
2.a brute force
Time complexity: O(n2)
Space complexity: O(n)
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
int sz = nums.length;
int[] cumuSum = new int[sz+1];
for(int i = 1; i <= sz; ++i) {
cumuSum[i] = cumuSum[i-1] + nums[i-1];
}
for(int i = 0; i <= sz; ++i) {
for(int j = i+2; j <= sz; ++j) {
if(k == 0) {
if(cumuSum[j] - cumuSum[i] == 0) {
return true;
}
}
else if((cumuSum[j] - cumuSum[i]) % k == 0) {
return true;
}
}
}
return false;
}
}
2.b Take the hashMap solution used in Subarray Sum Equals K LT560, we can store (cumuSum, index of the cumuSum) as map entry, for each new element in the array, firstly adding it to get the cumuSum, if k!= 0, cumuSum = cumuSum%mod, then return true if hashMap has the same cumuSum and i - (index+1) + 1 >= 2, since the subarray[index+1..i], only add cumuSum to the map when the cumuSum does not exist(which handles the case nums = [0, 0], k = 0; nums= [0, 5, 5], k = 5), othwise it will overwrite the previous position.
Note to deal the case when cumuSum[0..i] = n * k, after moduler operation, the mod becomes 0, so we have to put a pair with key = 0 to the map, the leftmost index for a subarray with size to be at least two is i = 1, i - index >= 2, hence the value = -1.
Time complexity: O(n)
Space complexity: O(n), not O(k) take nums = {1,1,1,1,1} and k = 0, generally it's O(k) is k != 0
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> sumIndex = new HashMap<>();
sumIndex.put(0, -1);
int sum = 0;
for(int i = 0; i < nums.length; ++i) {
sum += nums[i];
if(k != 0) {
sum = sum%k;
}
Integer index = sumIndex.get(sum);
if(index != null) {
if(i - index >= 2) {
return true;
}
}
else sumIndex.put(sum, i);
}
return false;
}
}
Idea 2.c: Set. Since the size of the subarray is required to be at least 2, we can't store the cumuSum immediately, need to make the gap and store the previous sum ending at i-1 at the end of index i, hence at the start of next index (i+1), the sum stored in the set is at least 2 steps away.
Time complexity: O(n)
Space complexity: O(n)
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
Set<Integer> sumMap = new HashSet<>();
int prev = 0;
int sum = 0;
for(int i = 0; i < nums.length; ++i) {
sum += nums[i];
if(k != 0) {
sum = sum%k;
}
if(sumMap.contains(sum)) {
return true;
}
sumMap.add(prev);
prev = sum;
}
return false;
}
}