LeetCode_前缀和_哈希表_中等_523.连续的子数组和

一时失言乱红尘 2023-10-06 23:21 6阅读 0赞

#### 目录 ####

*  1.题目
 *  2.思路
 *  3.代码实现（Java）

## 1.题目 ##

给你一个整数数组 nums 和一个整数 k ，编写一个函数来判断该数组是否含有同时满足下述条件的连续子数组：  
子数组大小至少为 2 ，且子数组元素总和为 k 的倍数。

如果存在，返回 true ；否则，返回 false 。  
如果存在一个整数 n ，令整数 x 符合 x = n \* k ，则称 x 是 k 的一个倍数。0 始终视为 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

来源：力扣（LeetCode）  
链接：https://leetcode.cn/problems/continuous-subarray-sum  
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

## 2.思路 ##

（1）前缀和数组  
常规想法是使用前缀和数组，即 preSum\[i\] 保存 nums\[0…i - 1\] 的前缀和，然后再使用两层 for 循环来遍历**长度大于等于 2 的子数组**，并判断其元素总和是否为 k 的倍数，如果符合条件，则直接返回 true，否则继续遍历。如果遍历结束后仍未找到，则返回 false。但是在 LeetCode 上提交时会出现“超出时间限制”的提示！**这说明该方法（时间复杂度为 O(n2)）还需优化，具体优化方法见思路 2**。

（2）前缀和数组 & 同余定理 & 哈希表  
思路参考[本题官方题解][Link 1]。

① 同余定理：  
**给定一个正整数 m，如果两个整数 a 和 b 满足 a - b 能够被 m 整除，即 (a - b) / m 得到一个整数，那么就称整数 a 与 b 对模 m 同余，记作 a ≡ b (mod m)。对模 m 同余是整数的一个等价关系。**

② 这里承接思路 1 代码中的前缀和数组 preSum，

根据同余定理，由 (preSum[j] - preSum[i]) % k == 0 可推出 preSum[j] % k == preSum[i] % k，继续推导可得：
    preSum[i] % k = (nums[0] + nums[1] + ... +nums[i - 1]) % k = (nums[0] % k + nums[1] % k + ... +nums[i - 1] % k ) % k 
    preSum[j] % k = (nums[0] + nums[1] + ... +nums[j - 1]) % k = (nums[0] % k + nums[1] % k + ... +nums[j - 1] % k ) % k 
    这里 j > i，显然当 preSum[j] % k 出现时，preSum[i] % k 一定存在，这一点可以作为后面遍历中判断的依据！

③ 定义哈希表 hashMap，key 对应 preSum\[i\] % k，value 对应 i

④ 遍历过程如下：  
计算 preSum\[j\] % k，并判断 preSum\[j\] % k 是否存在于 hashMap：  
**如果存在**，则说明此时一定存在 preSum\[i\] % k == preSum\[j\] % k (j > i)，此时再通过 key(preSum\[j\] % k) 取到对应的 value (i)，并判断 j - i ≥ 2 是否成立，若成立，则找到了满足题目要求的连续数组，直接返回 true 即可；  
**如果不存在**，则将 (preSum\[j\] % k, i) 作为键值对存入 hashMap 中；

⑤ 如果遍历结束仍未找到符合要求的子数组，则最后返回 false。

这里需要注意的是，由于在计算 preSum\[j\] % k = (preSum\[j - 1\] + nums\[j\]) % k 时，当前的 preSum\[j\] 只与 preSum\[j - 1\] 和 nums\[j\] 有关，且 nums\[j\] 已知，所以在代码中可以直接使用变量来代替数组，这样可以降低空间复杂度。

## 3.代码实现（Java） ##

//思路1————前缀和数组
    class Solution {
        
        public boolean checkSubarraySum(int[] nums, int k) {
        
            int length = nums.length;
            if (length < 2) {
        
                return false;
            }
            //preSum[i]:保存 nums[0...i - 1] 的前缀和
            int[] preSum = new int[length + 1];
            for (int i = 1; i < length + 1; i++) {
        
                preSum[i] = preSum[i - 1] + nums[i - 1];
            }
            for (int i = 0; i < length; i++) {
        
                for (int j = i + 2; j < length + 1; j++) {
        
                    //preSum[j] - preSum[i] 表示子数组 nums[i...j) 的元素和（这里已经控制子数组的长度大于等于 2）
                    if ((preSum[j] - preSum[i]) % k == 0) {
        
                        return true;
                    }
                }
            }
            return false;
        }
    }

//思路2————前缀和数组 & 同余定理 & 哈希表
    class Solution {
        
        public boolean checkSubarraySum(int[] nums, int k) {
        
            int length = nums.length;
            if (length < 2) {
        
                return false;
            }
            Map<Integer, Integer> hashMap = new HashMap<>();
            hashMap.put(0, -1);
            int remainder = 0;
            for (int j = 0; j < length; j++) {
        
                remainder = (remainder + nums[j]) % k;
                if (hashMap.containsKey(remainder)) {
        
                    int i = hashMap.get(remainder);
                    if (j - i >= 2) {
        
                        return true;
                    }
                } else {
        
                    hashMap.put(remainder, j);
                }
            }
            return false;
        }
    }

[Link 1]: https://leetcode.cn/problems/continuous-subarray-sum/solution/lian-xu-de-zi-shu-zu-he-by-leetcode-solu-rdzi/