2026-03-20统计有序数组中可被 K 整除的子数组数量。用go语言给定一个非降序排列的整数数组 nums以及一个正整数 k。定义如果数组中一段连续、非空的子数组它所有元素的和能被 k 整除那么这个子数组就是良好子数组。要求统计数组中所有不同的良好子数组的个数只要子数组的位置 / 序列不同就算不同的子数组。1 nums.length 100000。1 nums[i] 1000000000。nums 为非降序排列。1 k 1000000000。输入 nums [1,2,3], k 3。输出 3。解释良好子数组为 [1, 2]、[3] 和 [1, 2, 3]。例如[1, 2, 3] 是良好的因为其元素和为 1 2 3 6且 6 % k 6 % 3 0。题目来自力扣3729。代码执行过程详细分步描述nums[1,2,3]k3首先明确核心知识点良好子数组连续子数组和能被 k 整除前缀和sum[i]表示数组前 i 个元素的累加和子数组[j1, i]的和 sum[i] - sum[j]整除判定(sum[i] - sum[j]) % k 0等价于sum[i] % k sum[j] % k数组是非降序的存在连续相同数字段代码利用这个特性优化统计。初始状态前缀和计数器cnt{0:1}初始化0的余数对应前缀和为0的情况是子数组判定的基础当前前缀和sum0连续相同段起始下标lastStart0答案ans0数组元素[1, 2, 3]k3第一步遍历第1个元素下标i0值x1条件判断i0不成立不执行连续段统计逻辑更新前缀和sum 0 1 1计算余数1 % 3 1查询计数器cnt中余数1的数量为0答案累加ans 0 0 0当前状态sum1ans0lastStart0cnt{0:1}第二步遍历第2个元素下标i1值x2条件判断i0成立且x2 ! nums[0]1说明上一个连续段仅元素1结束统计上一段上一段长度1-01将对应前缀和余数加入计数器上一段前缀和s1余数1%31计数器cnt[1]变为1更新连续段起始lastStart 1更新前缀和sum 1 2 3计算余数3 % 3 0查询计数器cnt[0]1答案累加ans 0 1 1当前状态sum3ans1lastStart1cnt{0:1, 1:1}第三步遍历第3个元素下标i2值x3条件判断i0成立且x3 ! nums[1]2说明上一个连续段仅元素2结束统计上一段上一段长度2-11将对应前缀和余数加入计数器上一段前缀和s3余数3%30计数器cnt[0]变为2更新连续段起始lastStart 2更新前缀和sum 3 3 6计算余数6 % 3 0查询计数器cnt[0]2答案累加ans 1 2 3当前状态sum6ans3lastStart2cnt{0:2, 1:1}遍历结束最终答案为3与题目输出一致。核心逻辑总结利用前缀和余数相等的数学规律快速判断子数组和能否被k整除利用数组非降序的特性将连续相同的数字作为一个整体统计避免重复计算遍历过程中每遇到不同数字就把上一段连续数字的前缀和余数存入计数器再用当前前缀和余数匹配计数器累加符合条件的子数组数量。时间复杂度 额外空间复杂度1. 时间复杂度O(n)数组仅遍历一次每个元素只会被加入计数器一次没有嵌套循环总操作次数与数组长度n成正比是线性时间复杂度。2. 额外空间复杂度O(min(n, k))核心占用空间是余数计数器map存储的是前缀和的余数余数的取值范围只有0 ~ k-1最多存储min(n, k)个键值对其他变量sum、lastStart、ans都是常数级空间实际场景中k可能很大空间复杂度等价于O(n)。总结执行过程遍历数组→分段统计连续相同元素→更新前缀和→匹配余数计数器→累加答案时间复杂度O(n)线性复杂度适配10万长度的数组额外空间复杂度O(min(n, k))最优的空间优化方案。Go完整代码如下packagemainimport(fmt)funcnumGoodSubarrays(nums[]int,kint)(ansint64){cnt:map[int]int{0:1}// 为什么加个 0见 560 题sum:0// 前缀和lastStart:0// 上一个连续相同段的起始下标fori,x:rangenums{ifi0x!nums[i-1]{// 上一个连续相同段结束可以把上一段对应的前缀和添加到 cnts:sumforrangei-lastStart{cnt[s%k]s-nums[i-1]}lastStarti}sumx ansint64(cnt[sum%k])}return}funcmain(){nums:[]int{1,2,3}k:3result:numGoodSubarrays(nums,k)fmt.Println(result)}Python完整代码如下# -*-coding:utf-8-*-fromtypingimportListdefnum_good_subarrays(nums:List[int],k:int)-int: 计算好子数组的个数 好子数组定义子数组的和能被 k 整除 参数: nums: 整数数组 k: 除数 返回: 好子数组的个数 cnt{0:1}# 前缀和余数的计数器初始化0出现1次prefix_sum0# 当前前缀和last_start0# 上一个连续相同段的起始下标ans0fori,xinenumerate(nums):# 如果当前元素与前一个元素不同说明上一个连续段结束ifi0andx!nums[i-1]:# 处理上一个连续相同段sprefix_sum# 将上一段中所有可能的前缀和余数添加到计数器for_inrange(i-last_start):cnt[s%k]cnt.get(s%k,0)1s-nums[i-1]last_starti prefix_sumx# 当前前缀和余数在计数器中出现的次数就是好子数组的个数anscnt.get(prefix_sum%k,0)returnansdefmain():nums[1,2,3]k3resultnum_good_subarrays(nums,k)print(result)if__name____main__:main()C完整代码如下#includeiostream#includevector#includeunordered_mapusingnamespacestd;longlongnumGoodSubarrays(vectorintnums,intk){unordered_mapint,intcnt;cnt[0]1;// 为什么加个 0见 560 题intsum0;// 前缀和intlastStart0;// 上一个连续相同段的起始下标longlongans0;for(inti0;inums.size();i){intxnums[i];if(i0x!nums[i-1]){// 上一个连续相同段结束可以把上一段对应的前缀和添加到 cntintssum;for(intj0;ji-lastStart;j){cnt[s%k];s-nums[i-1];}lastStarti;}sumx;anscnt[sum%k];}returnans;}intmain(){vectorintnums{1,2,3};intk3;longlongresultnumGoodSubarrays(nums,k);coutresultendl;return0;}