Understand the problem of continuous subarray sum-CodePudding

Here is the

My solution:

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int sum = 0;
        int mod = 0;
        boolean isPresent = false;
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i =0; i<nums.length; i  ) {
            sum = sum   nums[i];
            mod = sum%k;
            if((mod==0 && i!=0) || (map.containsKey(mod) && (i - map.get(mod))>1)) {
                isPresent = true;
                break;
            }
            map.put(mod, i);
        }
        return isPresent;
    }
}

CodePudding user response：

Solution

You have a neat solution. Just a little modification should solve the problem. But, first of all there should be no objection to the fact that [0, 0] is a subarray that is visible by any given k. Actually, your solution can cover such cases too, with just one modification:

if(map.get(mod) == null) map.put(mod, i);

Reasoning

If a mod is present in the map, we shouldn't update it unnecessarily. It may lead to an error in cases like nums = [5, 0, 0, 0] and k = 3. Here is how:
For each iteration these are the variables:
at i = 0 --> at the end put (5, 0) to the map.
at i = 1 --> at the end put (5, 1) to the map.
at i = 2 --> at the end put (5, 2) to the map.
at i = 3 --> at the end put (5, 3) to the map.
In each step, you update the (mod, i) pair. As a result, (i - map.get(mod))>1) always gives false. Not updating the corresponding i value if the mod is already present in the map should solve the problem.

One might argue why not get rid of (i - map.get(mod))>1) part?
Well because it's used for cases like: nums = [1,0] and key = 2.

Extra

Your code takes 33 ms for runtime and approximately 128 MB for memory. With just one little modification, you can make it much better.
Just get rid of the isPresent variable and return true in the if condition. Return false outside the for loop. With these, on Leetcode it takes 17 ms to complete and 54 MB approximately. Exact numbers might vary from computer to computer.

CodePudding user response：

Looking at the subarray [0,0,0] the sum is 0 and 0 is divisible by any integer.

The problem with your implementation is, that it's subarrays can only start at the first element. When you add a second for-loop around your current loop that changes the start-element, you will find a solution.