Medium

题目描述

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

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

注意：

  • 子数组是数组中的一个连续的部分。
  • 如果存在一个整数 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 <= 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= sum(nums[i]) <= 2^31 - 1
  • 1 <= k <= 2^31 - 1

解题思路

这道题要求找到长度至少为2且元素和为k倍数的连续子数组。

核心思路：前缀和 + 哈希表

关键洞察：如果两个前缀和对k取模的结果相同，那么这两个位置之间的子数组和必定是k的倍数。

具体来说，如果 prefixSum[i] % k == prefixSum[j] % k（其中 i < j），那么子数组 nums[i+1...j] 的和就是k的倍数，因为： (prefixSum[j] - prefixSum[i]) % k = 0

算法步骤：

  1. 使用哈希表记录每个余数第一次出现的位置
  2. 初始化：map[0] = -1，表示前缀和为0的位置在-1（便于处理从索引0开始的子数组）
  3. 遍历数组，计算累积前缀和对k的余数
  4. 如果当前余数在哈希表中存在且距离至少为2，返回true
  5. 如果当前余数不在哈希表中，记录其位置

时间复杂度： O(n)，遍历一次数组 空间复杂度： O(min(n,k))，哈希表最多存储k个不同的余数

代码实现

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> modMap;
        modMap[0] = -1; // 初始化，处理从索引0开始的情况
        
        int prefixSum = 0;
        for (int i = 0; i < nums.size(); i++) {
            prefixSum += nums[i];
            int mod = prefixSum % k;
            
            if (modMap.find(mod) != modMap.end()) {
                if (i - modMap[mod] > 1) { // 确保子数组长度至少为2
                    return true;
                }
            } else {
                modMap[mod] = i;
            }
        }
        
        return false;
    }
};

class Solution:
    def checkSubarraySum(self, nums: List[int], k: int) -> bool:
        mod_map = {0: -1}  # 初始化，处理从索引0开始的情况
        
        prefix_sum = 0
        for i, num in enumerate(nums):
            prefix_sum += num
            mod = prefix_sum % k
            
            if mod in mod_map:
                if i - mod_map[mod] > 1:  # 确保子数组长度至少为2
                    return True
            else:
                mod_map[mod] = i
        
        return False

public class Solution {
    public bool CheckSubarraySum(int[] nums, int k) {
        Dictionary<int, int> modMap = new Dictionary<int, int>();
        modMap[0] = -1; // 初始化，处理从索引0开始的情况
        
        int prefixSum = 0;
        for (int i = 0; i < nums.Length; i++) {
            prefixSum += nums[i];
            int mod = prefixSum % k;
            
            if (modMap.ContainsKey(mod)) {
                if (i - modMap[mod] > 1) { // 确保子数组长度至少为2
                    return true;
                }
            } else {
                modMap[mod] = i;
            }
        }
        
        return false;
    }
}

var checkSubarraySum = function(nums, k) {
    const modMap = new Map();
    modMap.set(0, -1); // 初始化，处理从索引0开始的情况
    
    let prefixSum = 0;
    for (let i = 0; i < nums.length; i++) {
        prefixSum += nums[i];
        const mod = prefixSum % k;
        
        if (modMap.has(mod)) {
            if (i - modMap.get(mod) > 1) { // 确保子数组长度至少为2
                return true;
            }
        } else {
            modMap.set(mod, i);
        }
    }
    
    return false;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n)只需遍历数组一次
空间复杂度O(min(n,k))哈希表最多存储k个不同的余数值

相关题目