[JAVA] Use mode k with hashmap / T : O(N), S : O(k)


  • 0
    J

    If there was previous subarraysum with same mod value, than it will be divided by k.

    class Solution {
        public boolean checkSubarraySum(int[] nums, int k) {
            if(nums.length < 2)
                return false;
            
            HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
            int sum = 0;
            
            map.put(0, -1);
            for(int i = 0; i < nums.length; i++){
                sum += nums[i];
                
                if(k != 0)
                    sum %= k;
                // sum - subsum = k
                if(map.containsKey(sum)){
                    if((i - map.get(sum)) > 1) return true;
                }
                else{
                    map.put(sum, i); // next movement.
                }
            }
    
            return false; 
        }
    }
    

  • 0
    A

    @jaehoonlee88 Why check if k != 0 inside the loop everytime?


Log in to reply
 

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