LeetCode 3729. 统计有序数组中可被 K 整除的子数组数量

核心思路

本题的关键在于去重：两个子数组只要数值序列相同就视为同一个。由于数组有序，重复的子数组只能由连续相同的元素构成。

两步策略：

1. 统计全部（含重复）：用前缀和 + 哈希表统计所有和能被 k 整除的子数组
2. 减去重复计数：对每段连续相同元素，减去重复统计的子数组数量

---

解法一：直接枚举（易理解）AC

```javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numGoodSubarrays = function(nums, k) {
    // Step 1: 统计所有子数组（含重复）
    let ans = 0;
    let prefix = 0;
    const map = new Map();
    map.set(0, 1);
    
    for (let x of nums) {
        prefix = ((prefix + x) % k + k) % k;  // 处理负数
        const count = map.get(prefix) || 0;
        ans += count;
        map.set(prefix, count + 1);
    }
    
    // Step 2: 减去重复统计
    let i = 0;
    const n = nums.length;
    
    while (i < n) {
        let j = i + 1;
        while (j < n && nums[j] === nums[i]) j++;
        
        const m = j - i;      // 连续相同元素个数
        const val = nums[i];
        
        // 枚举所有可能的子数组长度
        for (let len = 1; len <= m; len++) {
            // 如果该长度组成的子数组和能被 k 整除
            if ((len * val) % k === 0) {
                // 该长度有 (m - len + 1) 个子数组，但在 step1 中统计了 m - len + 1 次
                // 只需要保留 1 个，所以要减去 m - len
                ans -= (m - len);
            }
        }
        
        i = j;
    }
    
    return ans;
};
```

---

解法二：数学优化（推荐）

利用 step = k / gcd(k, v) 跳跃枚举，避免遍历所有长度：

```javascript
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var numGoodSubarrays = function(nums, k) {
    // 特判：k=1 时所有子数组都满足，不同子数组数量 = n
    if (k === 1) return nums.length;
    
    // Step 1: 统计所有子数组（含重复）
    let ans = 0;
    let prefix = 0;
    const map = new Map();
    map.set(0, 1);
    
    for (let x of nums) {
        prefix = ((prefix + x) % k + k) % k;
        const count = map.get(prefix) || 0;
        ans += count;
        map.set(prefix, count + 1);
    }
    
    // Step 2: 减去重复统计
    const n = nums.length;
    let i = 0;
    
    while (i < n) {
        let j = i + 1;
        while (j < n && nums[j] === nums[i]) j++;
        
        const m = j - i;      // 连续相同元素个数
        const val = nums[i];
        
        // 数学优化：只需要枚举能被 k 整除的长度
        // 步长 step = k / gcd(k, val)
        const step = k / gcd(k, Math.abs(val));
        
        // 从 step 开始，每次增加 step，直到 m
        for (let len = step; len <= m; len += step) {
            ans -= (m - len);
        }
        
        i = j;
    }
    
    return ans;
};

// 最大公约数（辅助函数）
function gcd(a, b) {
    a = Math.abs(a);
    b = Math.abs(b);
    while (b !== 0) {
        [a, b] = [b, a % b];
    }
    return a;
}
```

---

详细示例

```javascript
// 示例 1
console.log(numGoodSubarrays([4,5,0,-2,-3,1], 5));
// 输出：7
// 解释：所有子数组和为 5 的倍数，去重后有 7 个

// 示例 2
console.log(numGoodSubarrays([1,1,1,1], 2));
// 输出：4
// 解释：和为偶数的不同子数组：[1,1], [1,1,1,1], 长度为2的段有2个但相同只算1个

// 示例 3
console.log(numGoodSubarrays([0,0,0,0], 3));
// 输出：4
// 解释：[0], [0,0], [0,0,0], [0,0,0,0] 共4个不同子数组
```

---

复杂度分析

解法 时间复杂度 空间复杂度
解法一 O(n + Σm) 最坏 O(n²) O(n)
解法二 O(n + Σ(m/step)) 最坏 O(n²) O(n)

---

关键细节

1. 前缀和取模：((prefix + x) % k + k) % k 确保余数非负
2. 去重逻辑：
   · 对于长度为 m 的连续相同段，长度为 len 的子数组有 (m - len + 1) 个
   · 步骤1统计了全部，我们只需要保留 1 个，所以减去 (m - len)
3. 数学优化：
   · len * val % k === 0 等价于 len 是 k / gcd(k, val) 的倍数
   · 只用枚举 len = step, 2*step, 3*step, ...
4. 边界情况：
   · val = 0 时，gcd(k, 0) = k，step = 1，所有长度都要去重
   · k = 1 时，直接返回 nums.length 即可

---

如果还想看其他语言的实现或有任何疑问，欢迎继续提问！