2026-03-20：统计有序数组中可被 K 整除的子数组数目。用go讲话，给定一个非降序罗列的整数数组 nums，以及一个正整数 k。
界说：淌若数组中一段贯串、非空的子数组，它统共元素的和能被 k 整除，那么这个子数组等于考究子数组。
要求：统计数组中统共不同的考究子数组的个数（只须子数组的位置 / 序列不同，就算不同的子数组）。
1
1
nums 为非降序罗列。
1
输入： 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]，k=3）
最初明确中枢常识点：
1. 考究子数组：贯串子数组和能被 k 整除；
2. 前缀和：sum[i] 暗意数组前 i 个元素的累加和，子数组 [j+1， i] 的和 = sum[i] - sum[j]；
3. 整除判定：(sum[i] - sum[j]) % k == 0 等价于 sum[i] % k == sum[j] % k；
4. 数组口角降序的，存在贯串调换数字段，代码诈欺这个特质优化统计。
运转景色
• 前缀和计数器 cnt：{0:1}（运回荡0的尾数，对应前缀和为0的情况，是子数组判定的基础）
• 现时前缀和 sum：0
• 贯串调换段肇始下标 lastStart：0
• 谜底 ans：0
• 数组元素：[1， 2， 3]，k=3
第一步：遍历第1个元素（下标i=0，值x=1）
1. 条款判断：i>0 不行就，不引申贯串段统计逻辑；
2. 更新前缀和：sum = 0 + 1 = 1；
3. 计较尾数：1 % 3 = 1，查询计数器cnt中尾数1的数目为0；
4. 谜底累加：ans = 0 + 0 = 0；
现时景色：sum=1，ans=0，lastStart=0，cnt={0:1}
第二步：遍历第2个元素（下标i=1，值x=2）
1. 条款判断：i>0 成就，且x=2 != nums[0]=1，阐发上一个贯串段（仅元素1）限制；
2. 统计上一段：上一段长度=1-0=1，将对应前缀和尾数加入计数器：
• 上一段前缀和s=1，尾数1%3=1，计数器cnt[1]变为1；
3. 更新贯串段肇始：lastStart = 1；
4. 更新前缀和：sum = 1 + 2 = 3；
5. 计较尾数：3 % 3 = 0，查询计数器cnt[0]=1；
6. 谜底累加：ans = 0 + 1 = 1；
现时景色：sum=3，ans=1，lastStart=1，cnt={0:1， 1:1}
第三步：遍历第3个元素（下标i=2，值x=3）
1. 条款判断：i>0 成就，OD体育app且x=3 != nums[1]=2，阐发上一个贯串段（仅元素2）限制；
2. 统计上一段：上一段长度=2-1=1，将对应前缀和尾数加入计数器：
• 上一段前缀和s=3，尾数3%3=0，计数器cnt[0]变为2；
3. 更新贯串段肇始：lastStart = 2；
4. 更新前缀和：sum = 3 + 3 = 6；
5. 计较尾数：6 % 3 = 0，查询计数器cnt[0]=2；
6. 谜底累加：ans = 1 + 2 = 3；
现时景色：sum=6，ans=3，lastStart=2，cnt={0:2， 1:1}
遍历限制
最终谜底为3，与题目输出一致。
中枢逻辑转头
1. 诈欺前缀和+尾数十分的数学王法，快速判断子数组和能否被k整除；
2. 诈欺数组非降序的特质，将贯串调换的数字看成一个举座统计，幸免重叠计较；
3. 遍历进程中，每遭受不同数字，就把上一段贯串数字的前缀和尾数存入计数器，再用现时前缀和尾数匹配计数器，累加适合条款的子数组数目。
时辰复杂度 & 出奇空间复杂度
1. 时辰复杂度：O(n)
• 数组仅遍历一次，每个元素只会被加入计数器一次；
• 莫得嵌套轮回，总操作次数与数组长度n成正比，是线性时辰复杂度。
2. 出奇空间复杂度：O(min(n， k))
• 中枢占用空间是尾数计数器map，存储的是前缀和的尾数；
• 尾数的取值鸿沟只好0 ~ k-1，最多存储min(n， k)个键值对；
• 其他变量（sum、lastStart、ans）齐是常数级空间；
• 实质场景中k可能很大，空间复杂度等价于O(n)。
转头
1. 引申进程：遍历数组→分段统计贯串调换元素→更新前缀和→匹配尾数计数器→累加谜底；
2. 时辰复杂度：O(n)（线性复杂度，适配10万长度的数组）；
3. 出奇空间复杂度：O(min(n， k))（最优的空间优化有策画）。
Go完好代码如下：
package main
import (
"fmt"
)
func numGoodSubarrays(nums []int， k int) (ans int64) {
cnt := map[int]int{0: 1} // 为什么加个 0？见 560 题
sum := 0 // 前缀和
lastStart := 0 // 上一个贯串调换段的肇始下标
for i， x := range nums {
if i > 0 && x != nums[i-1] {
// 上一个贯串调换段限制，不错把上一段对应的前缀和添加到 cnt
s := sum
forrange i - lastStart {
cnt[s%k]++
s -= nums[i-1]
}
lastStart = i
}
sum += x
ans += int64(cnt[sum%k])
}
return
}
func main {
nums := []int{1， 2， 3}
k := 3
result := numGoodSubarrays(nums， k)
fmt.Println(result)
}
Python完好代码如下：
# -*-coding:utf-8-*-
from typing import List
def num_good_subarrays(nums: List[int]， k: int) -> int:
"""
计较好子数组的个数
好子数组界说：子数组的和能被 k 整除
参数:
nums: 整数数组
k: 除数
复返:
好子数组的个数
"""
cnt = {0: 1} # 前缀和尾数的计数器，运回荡0出现1次
prefix_sum = 0 # 现时前缀和
last_start = 0 # 上一个贯串调换段的肇始下标
ans = 0
for i， x in enumerate(nums):
# 淌若现时元素与前一个元素不同，阐发上一个贯串段限制
if i > 0 and x != nums[i-1]:
# 处分上一个贯串调换段
s = prefix_sum
# 将上一段中统共可能的前缀和尾数添加到计数器
for _ in range(i - last_start):
cnt[s % k] = cnt.get(s % k， 0) + 1
s -= nums[i-1]
last_start = i
prefix_sum += x
# 现时前缀和尾数在计数器中出现的次数等于好子数组的个数
ans += cnt.get(prefix_sum % k， 0)
return ans
def main:
nums = [1， 2， 3]
k = 3
result = num_good_subarrays(nums， k)
print(result)
if __name__ == "__main__":
main
C++完好代码如下：
#include
#include
#include
using namespace std;
long long numGoodSubarrays(vector& nums， int k) {
unordered_map cnt;
cnt[0] = 1; // 为什么加个 0？见 560 题
int sum = 0; // 前缀和
int lastStart = 0; // 上一个贯串调换段的肇始下标
long long ans = 0;
for (int i = 0; i
int x = nums[i];
if (i > 0 && x != nums[i-1]) {
// 上一个贯串调换段限制，不错把上一段对应的前缀和添加到 cnt
int s = sum;
for (int j = 0; j
cnt[s % k]++;
s -= nums[i-1];
}
lastStart = i;
}
sum += x;
ans += cnt[sum % k];
}
return ans;
}
int main {
vector nums = {1， 2， 3};
int k = 3;
long long result = numGoodSubarrays(nums， k);
cout
return0;
}
咱们深信东说念主工智能为庸碌东说念主提供了一种“增强器具”，并勤勉于共享全方针的AI常识。在这里，您不错找到最新的AI科普著作、器具评测、擢升后果的隐私以及行业知悉。
迎接见谅“福大大架构师逐日一题”，发音讯可获取口试贵府OD体育app官网，让AI助力您的以前发展。
亚搏体育官方网站 - YABO