解题思路

本题在经典题目「974. 和可被 K 整除的子数组」基础上增加了去重要求：两个子数组只要数值序列相同即视为相同。

核心洞察：由于数组非降序，重复的子数组只可能由完全相同的连续元素组成。因此解题分两步：

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

对于一段连续相同元素，只有当子数组长度 h 满足 (h * v) % k == 0 时才会被重复统计。重复次数为 m - h。

---

Python3 代码实现

```python
from typing import List
from collections import Counter
from math import gcd

class Solution:
    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
        # Step 1: 统计所有和能被 k 整除的子数组（含重复）
        ans = 0
        prefix = 0
        cnt = Counter({0: 1})  # 前缀和余数为0初始出现1次
        
        for x in nums:
            prefix = (prefix + x) % k
            ans += cnt[prefix]   # 当前余数之前出现的次数即为新增子数组数
            cnt[prefix] += 1
        
        # Step 2: 减去重复统计的相同子数组
        n = len(nums)
        i = 0
        while i < n:
            j = i + 1
            while j < n and nums[j] == nums[i]:
                j += 1
            
            m = j - i          # 连续相同元素的个数
            v = nums[i]        # 该元素的值
            
            # 枚举所有可能长度 h，若 h * v 能被 k 整除则需去重
            # 优化：只枚举满足条件的 h，步长为 k / gcd(k, v)
            if k == 1:
                # k=1 时所有子数组都满足，直接减去全部重复
                ans -= m * (m + 1) // 2 - m
            else:
                step = k // gcd(k, v)
                for h in range(step, m + 1, step):
                    ans -= m - h
            
            i = j
        
        return ans
```

---

复杂度分析

指标 复杂度
时间复杂度 O(n + m/step)，最坏 O(n²)（全相同元素时）
空间复杂度 O(n)（哈希表存储前缀和余数）

对于全相同元素数组，虽然理论上界为 O(n²)，但实际运行中由于 step 通常较大，性能往往接近 O(n)。