# Java O(n) time O(k) space

• We iterate through the input array exactly once, keeping track of the running sum mod k of the elements in the process. If we find that a running sum value at index j has been previously seen before in some earlier index i in the array, then we know that the sub-array (i,j] contains a desired sum.

``````public boolean checkSubarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
int runningSum = 0;
for (int i=0;i<nums.length;i++) {
runningSum += nums[i];
if (k != 0) runningSum %= k;
Integer prev = map.get(runningSum);
if (prev != null) {
if (i - prev > 1) return true;
}
else map.put(runningSum, i);
}
return false;
}
``````

• Smart solution! I like it!

• @tankztc Thanks!

• Great solution! Thanks for sharing!

• I can't believe I just needed to get the modulus to get this method to work. I was scratching my head to figure out how to modify the runningSum method to work.

It looks so simple now. I feel so stupid.

Any suggestions guys how I can improve. I mean there is this leetcode question which is a variant of this and it asks to make the sum exactly equal to target instead of multiple of it. I used the same method for that problem. However, for this, question I couldn't modify the running sum method to work. I feel dumb

• Cool!
Could you explain

``````{{put(0,-1);}};
``````

in

``````Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};
``````

?
Thanks

• The main idea is that (x + n*k) mod k = x ,which x can be 0,1,...,k-1.

• @BryanBo.Cao , I think it initialized the map with `map.put(0,-1)`.

"Double brace initialisation creates an anonymous class derived from the specified class (the outer braces), and provides an initialiser block within that class (the inner braces)." - Quoted from Stackoverflow

• @tankztc Cool thanks!
So we could actually omit the last ';' in

``````Map<Integer, Integer> map = new HashMap<Integer, Integer>(){{put(0,-1);}};;
``````

Anyway, it's just about the syntax.

• Nice solution taking advantage of "non-negative integer"!

• said in Java O(n) time O(k) space:

if (prev != null) {
if (i - prev > 1) return true;
}

Sorry, I'm still having trouble understanding this part. Can someone explain why we need to check the indices and what it means?

• @huyanhh This is to make sure that the sub-array is of at least length 2.

• @compton_scatter

I'm going through your solution with the input [23, 2, 6, 4, 7], k=6, but it seems like I keep messing up.

When I'm at index 3, the map looks like {0:-1, 5:0, 1:1} and runningSum should be 5 so I look up 5 in the map, but then doing i-prev gives me 3, which will return true without checking 7, but shouldn't I check the last one as the subarray needs to include the entire array? Where am I getting this wrong?

• @huyanhh The sum of subarray [2,6,4] is 12, which is a multiple of 6.

• @compton_scatter ohh that makes a lot of sense. Thanks!

• Smart...Now that with this solution we even didn't need to consider those annoying corner cases like [0,0] 100 -> true...

• ``````    if (k != 0) runningSum %= k;
``````

This is smart.

• @shawngao Alternatively, do `if (k == 0) k = 0x80000000;` before the loop and delete the `if (k != 0)` :-)

• I don't understand that why "running sum value at index j has been previously seen before in some earlier index i in the array" can help us decide there's a desired subarray in it?? Could you please kindly explain it? Thanks much @compton_scatter

• @ohuohuo This is one of those magics of remainder theorem :)

(a+(n*x))%x is same as (a%x)

For e.g. in case of the array [23,2,6,4,7] the running sum is [23,25,31,35,42] and the remainders are [5,1,1,5,0]. We got remainder 5 at index 0 and at index 3. That means, in between these two indexes we must have added a number which is multiple of the k. Hope this clarifies your doubt :)

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.