523. Continuous Subarray Sum (https://leetcode.com/problems/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.

523. Continuous Subarray Sum (#1 Array + Brutal force).java

// Array + Brutal force solution
// Time: O(n ^ 2), 16ms
// Space: O(1), 42.2mb
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        for(int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            
            for(int j = 1; i + j < nums.length; j++) {
                sum += nums[i + j];
                
                // !!: Take care of the corner case when k == 0
                if(k == 0) {
                    if(sum == 0) return true;
                    
                } else if(sum % k == 0) {
                    return true;
                }
            }
        }
        
        return false;
    }
}

523. Continuous Subarray Sum (#1 Array + Hash table).java

// Array + Hash table solution: store sum % k in the hash table; idea like 1010 #2
// Time: O(n), 2ms
// Space: O(min(k, n)), 42.3mb
class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        // Init map of <prefix sum % k, end index (including)>
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        
        int sum = 0;
        for(int i = 0; i < nums.length; i++) {
            sum += nums[i];
            int mod = k != 0 ? sum % k : sum;
            
            // Look up the map
            if(map.containsKey(mod)) {
                if(i - map.get(mod)> 1) return true;
                
            } else {
                // Update the map
                map.put(mod, i);
            }

        }
        
        return false;
    }
}