(sum %= k) 523. Continuous Subarray Sum

T: O(n)
S: O(n)

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);

        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            sum %= k; // store remainder!
            
            if (map.containsKey(sum)) {
                if (i - map.get(sum) > 1) { // means keep the previous sum index, not update same sum with latest i
                    return true;
                }
            } else {
                map.put(sum, i); // only when not in map, update the index (for keeping the oldest index to make longer dist)
            }
        }
        return false;
    }
}

/***
T: O(n)
S: O(n)

0. 1 2
23 2 4

set(23, 25, 29)

23%6 = 5

5 0
1
5

 */