😁523 continuous subarray sum

https://leetcode.com/problems/continuous-subarray-sum/

n^2会超时，其实思路类似2sum，

sum = prefix[j] - prefix[i] + nums[i] = prefix[j] - (prefix[i] - nums[i])，所以要想sum % k == 0，只需要prefix[j]和prefix[i] - nums[i]两部分模k相等就可以

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int[] prefixes = new int[nums.length];
        prefixes[0] = nums[0];
        for (int i = 1; i < nums.length; i++) {
            prefixes[i] = prefixes[i - 1] + nums[i];
        }
        // p[j] - p[i] + nums[i] = k * a
        // p[j] = p[i] - nums[i] + k*a
        Set<Integer> set = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            if (set.contains((prefixes[i]) % k)) 
                return true;
            int key = prefixes[i] - nums[i];
            set.add(key % k);
        }
        return false;
    }
}

class Solution {
    // pj - pi + ni = kn
    // pi-ni = pj - kn ==> 两边的余数也应该相同, 又因为kn%k=0,因此pi-ni和pj的余数应该相同
    // 对每一个psum，把它看作pj时，看看它有没有之前对应的pi-ni
    // 把它看作pi时，把pi-ni的余数存进set里
    
    // ni保证了至少两个元素，这代表了i一定被包含进去了，如果直接用nj-ni那么i等于j-1的时候就没有被包括进去
    public boolean checkSubarraySum(int[] nums, int k) {
        int[] psum = new int[nums.length];
        Set<Integer> set = new HashSet<>();
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            psum[i] = sum;
            if (i > 0 && psum[i] % k == 0) {
                return true;
            }
            if (set.contains(psum[i]%k)) {
                return true;
            }
            set.add((psum[i]-nums[i])%k);
        }
        return false;
    }
}