连续的子数组和

523. 连续的子数组和

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

• 子数组大小 至少为 2 ，且
• 子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。

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

示例 1：

输入：nums = [23,2,4,6,7], k = 6
输出：true
解释：[2,4] 是一个大小为 2 的子数组，并且和为 6 。

示例 2：

输入：nums = [23,2,6,4,7], k = 6
输出：true
解释：[23, 2, 6, 4, 7] 是大小为 5 的子数组，并且和为 42 。 
42 是 6 的倍数，因为 42 = 7 * 6 且 7 是一个整数。

示例 3：

输入：nums = [23,2,6,4,7], k = 13
输出：false

提示：

• 1 <= nums.length <= 105
• 0 <= nums[i] <= 109
• 0 <= sum(nums[i]) <= 231 - 1
• 1 <= k <= 231 - 1

方法一：前缀和+哈希表

使用暴力直接枚举所有大小大于 2 的子数组，判断子数组和是否为 k 的倍数。这样做时间复杂度为 O(n^3)。

我们可以使用前缀和，这样就可以在 O(1) 时间内判断子数组和是否为 k 的倍数。

用 prefixSum[i] 表示 nums 从下标 0 到下标 i 的前缀和，则 nums 从下标 p + 1 到下标 q 的子数组长度为 q - p，该子数组的元素和为 prefixSum[q] - prefixSum[p]。

如果 prefixSum[q] - prefixSun[p] 为 k 的倍数，且 q - p >= 2，则上述子数组即满足大小至少为 2 且元素和为 k 的倍数。

我们只需保存每个下标对应的前缀和除 k 的余数即可，使用哈希表存储每个余数第一次出现的下标。

规定空的前缀的结束下标为 -1，在哈希表中存入键值对(0, -1)。从小到大依次遍历每个 i ，计算每个下标对应的前缀和除以 k 的余数，并维护哈希表。

class Solution {
    public boolean checkSubarraySum(int[] nums, int k) {
        int n = nums.length;
        if(n < 2){
            return false;
        }
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1);
        int remainder = 0;
        for(int i = 0; i < n; i++){
            remainder = (remainder + nums[i]) % k; //计算前缀和除 k 的余数
            if(map.containsKey(remainder)){//如果存在余数，直接减去见面这个子数组就能得到和为 k 的倍数的子数组
                int preIndex = map.get(remainder);
                if(i - preIndex >= 2){
                    return true;
                }
            } else{
                map.put(remainder, i);
            }
        }
        return false;
    }
}

• 时间复杂度O(m)，m 是数组 nums 的长度
• 空间复杂度最大O(m)