Leetcode 523

523. 连续的子数组和

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：

子数组大小 至少为2 ，且子数组元素总和为 k 的倍数。如果存在，返回 true ；否则，返回 false 。

如果存在一个整数 n ，令整数 x 符合 x = n * k ，则称 x 是 k 的一个倍数。

public boolean checkSubarraySum(int[] nums, int k) {
    int n = nums.length;
    if (n < 2) {//大小至少为2
        return false;
    }
    //利用了同余定理
    //即 ( pre(j) - pre (i) ) % k == 0 则 pre(j) % k == pre(i) % k
    //推导 => pre (i) % k = (a0 + a1 + ... + ai) % k = (a0 % k + a1 % k + ... ai % k ) % k
    //（该推导在简化前缀和的时候有用，说明当前前缀和 % k 不会影响后面的前缀和 % k ）
    Map<Integer, Integer> map = new HashMap<>();
    map.put(0, -1);
    int res = 0;
    for (int i = 0; i < n; i++) {
        res = (res + nums[i]) % k;//前缀和 取模
        if (map.containsKey(res)) {
            int pre = map.get(res);
            if (i - pre >= 2) {
                //即子数组满足 len大小>=2 且 元素和为k的倍数
                return true;
            }
        } else {
            map.put(res, i);
        }
    }
    return false;
}