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

Categories:

题目描述
思路分析
1. 解法一：前缀和 + 余数计数（推荐）
相似题目

题目描述

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

思路分析

解法一：前缀和 + 余数计数（推荐）

核心思路：

若 (pre[j] - pre[i]) % k == 0，则 pre[i] % k == pre[j] % k。

统计每个余数出现次数，当前余数出现 cnt 次，可形成 cnt 个满足条件的子数组。

注意余数可能为负数，需要统一转为非负。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(k)，其中 k 表示取模基数。

class Solution {
    public int subarraysDivByK(int[] nums, int k) {
        int[] cnt = new int[k];
        cnt[0] = 1;

        int sum = 0;
        int ans = 0;

        for (int num : nums) {
            sum = (sum + num) % k;
            if (sum < 0) {
                sum += k;
            }
            ans += cnt[sum];
            cnt[sum]++;
        }

        return ans;
    }
}

func subarraysDivByK(nums []int, k int) int {
	cnt := make([]int, k)
	cnt[0] = 1

	sum := 0
	ans := 0

	for _, v := range nums {
		sum = (sum + v) % k
		if sum < 0 {
			sum += k
		}
		ans += cnt[sum]
		cnt[sum]++
	}

	return ans
}

相似题目

题目	难度	考察点
560. 和为 K 的子数组	中等	前缀和、哈希表
523. 连续的子数组和	中等	前缀和、同余
525. 连续数组	中等	前缀和、哈希表
930. 和相同的二元子数组	中等	前缀和、滑动窗口
1248. 统计「优美子数组」	中等	前缀和、双指针

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2025/22987955