解题思路本题在经典题目「974. 和可被 K 整除的子数组」基础上增加了去重要求两个子数组只要数值序列相同即视为相同。核心洞察由于数组非降序重复的子数组只可能由完全相同的连续元素组成。因此解题分两步1. 统计全部含重复用前缀和 哈希表统计所有和能被 k 整除的子数组数量2. 减去重复计数遍历数组对每一段连续相同元素长度为 m值为 v减去其中被重复统计的子数组数量对于一段连续相同元素只有当子数组长度 h 满足 (h * v) % k 0 时才会被重复统计。重复次数为 m - h。---Python3 代码实现pythonfrom typing import Listfrom collections import Counterfrom math import gcdclass Solution:def numGoodSubarrays(self, nums: List[int], k: int) - int:# Step 1: 统计所有和能被 k 整除的子数组含重复ans 0prefix 0cnt Counter({0: 1}) # 前缀和余数为0初始出现1次for x in nums:prefix (prefix x) % kans cnt[prefix] # 当前余数之前出现的次数即为新增子数组数cnt[prefix] 1# Step 2: 减去重复统计的相同子数组n len(nums)i 0while i n:j i 1while j n and nums[j] nums[i]:j 1m j - i # 连续相同元素的个数v nums[i] # 该元素的值# 枚举所有可能长度 h若 h * v 能被 k 整除则需去重# 优化只枚举满足条件的 h步长为 k / gcd(k, v)if k 1:# k1 时所有子数组都满足直接减去全部重复ans - m * (m 1) // 2 - melse:step k // gcd(k, v)for h in range(step, m 1, step):ans - m - hi jreturn ans---复杂度分析指标 复杂度时间复杂度 O(n m/step)最坏 O(n²)全相同元素时空间复杂度 O(n)哈希表存储前缀和余数对于全相同元素数组虽然理论上界为 O(n²)但实际运行中由于 step 通常较大性能往往接近 O(n)。