当前位置：首页 > article >正文

Leetcode.974 和可被 K 整除的子数组

article 2024/11/17 18:22:36

题目链接

Leetcode.974 和可被 K 整除的子数组 rating : 1676

题目描述

给定一个整数数组 $n u m s$ 和一个整数 $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

提示：

$\leq nums.length \leq 3 * 10^4$
$-10^4 \leq nums[i] \leq 10^4$
$\leq k \leq 10^4$

解法：前缀和 + 哈希表

我们假设 $[j, i]$ 区间的子数组元素和可以被 $k$ 整除，即 :

$nums[i])\ mod\ k = 0$

我们用 $s u m$ 表示 $n u m s$ 的前缀和数组，可将上式转换为：

$sum[j-1])\ mod\ k = 0$

再转换一下得到：

$sum[j-1]\ mod\ k= sum[i]\ mod\ k$

那么以 $n u m s [i]$ 为结尾的数组，我们只需要统计前面等于 $sum[j-1]\ mod\ k$ 也就是 $sum[i]\ mod\ k$ 的数量 $t$ 即可。

那么这个 $t$ 就是以 $n u m s [i]$ 为结尾的数组中和能被 $k$ 整除的子数组的数量。

我们只需要对每一个 $n u m s [i]$ 都加上 $t$ 即可，这样我们就可以统计出所有的和能被 $k$ 整除的子数组的数量。

在实现上，我们使用哈希表来记录前缀和出现的次数。初始时，和为 $0$ ，也需要统计它的出现次数，即 ${ 0 , 1 \}$ 。

注意：由于 $n u m s$ 中存在负数，所以 $sum\ mod\ k$ 仍然有可能是负数，所以我们要将其转换为正数，即：

$(sum\ mod\ k + k)\ mod\ k$

时间复杂度： $O (n)$

C++代码：

class Solution {
public:
    int subarraysDivByK(vector<int>& nums, int k) {
        int n = nums.size();
        int ans = 0 , sum = 0;
        unordered_map<int,int> cnt{{0,1}};

        for(int i = 0;i < n;i++){
            sum += nums[i];
            auto key = (sum % k + k) % k;
            ans += cnt[key];
            cnt[key]++;
        }

        return ans;
    }
};