企业官网建设流程全解析

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 即可

---

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