Medium

题目描述

给定一个整数数组 nums 和一个整数 k，返回和可被 k 整除的非空子数组的数目。

子数组是数组的连续部分。

示例 1：

输入：nums = [4,5,0,-2,-3,1], k = 5
输出：7
解释：有 7 个和可被 k = 5 整除的子数组：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]

示例 2：

输入：nums = [5], k = 9
输出：0

提示：

  • 1 <= nums.length <= 3 * 10^4
  • -10^4 <= nums[i] <= 10^4
  • 2 <= k <= 10^4

解题思路

推荐解法：前缀和 + 哈希表

这道题的关键洞察是：如果两个前缀和对 k 的余数相同，那么它们之间的子数组和一定能被 k 整除。

具体思路：

  1. 维护前缀和的模 k 余数
  2. 使用哈希表记录每个余数出现的次数
  3. 当遇到某个余数时，说明之前出现过相同余数的前缀和，它们之间的所有子数组都满足条件

需要注意的细节：

  • 初始化时，余数 0 的计数为 1（表示空前缀）
  • 处理负数余数：在某些语言中 -1 % 5 = -1，需要转换为正数 (-1 + 5) % 5 = 4
  • 每次遇到已存在的余数时，答案增加该余数之前出现的次数

时间复杂度 O(n)，空间复杂度 O(min(n,k))，是最优解法。

其他解法：

  • 暴力解法：枚举所有子数组，时间复杂度 O(n²)，会超时

代码实现

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        count[0] = 1;
        
        int sum = 0, result = 0;
        for (int num : nums) {
            sum += num;
            int remainder = ((sum % k) + k) % k;
            result += count[remainder];
            count[remainder]++;
        }
        
        return result;
    }
};

class Solution:
    def subarraysDivByK(self, nums: List[int], k: int) -> int:
        count = {0: 1}
        prefix_sum = 0
        result = 0
        
        for num in nums:
            prefix_sum += num
            remainder = prefix_sum % k
            result += count.get(remainder, 0)
            count[remainder] = count.get(remainder, 0) + 1
        
        return result

public class Solution {
    public int SubarraysDivByK(int[] nums, int k) {
        Dictionary<int, int> count = new Dictionary<int, int>();
        count[0] = 1;
        
        int sum = 0, result = 0;
        foreach (int num in nums) {
            sum += num;
            int remainder = ((sum % k) + k) % k;
            if (count.ContainsKey(remainder)) {
                result += count[remainder];
                count[remainder]++;
            } else {
                count[remainder] = 1;
            }
        }
        
        return result;
    }
}

var subarraysDivByK = function(nums, k) {
    const count = new Map();
    count.set(0, 1);
    
    let sum = 0, result = 0;
    for (const num of nums) {
        sum += num;
        let remainder = ((sum % k) + k) % k;
        result += count.get(remainder) || 0;
        count.set(remainder, (count.get(remainder) || 0) + 1);
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n)
空间复杂度O(min(n, k))

说明：

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

相关题目