2026-03-20：统计有序数组中可被 K 整除的子数组数量。用go语言，给定一个非降序排列的整数数组 nums，以及一个正整数 k。 定义：如果数

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)
}

# -*-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()

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

long long numGoodSubarrays(vector<int>& nums, int k) {
    unordered_map<int, int> cnt;
    cnt[0] = 1; // 为什么加个 0？见 560 题
    int sum = 0; // 前缀和
    int lastStart = 0; // 上一个连续相同段的起始下标
    long long ans = 0;

    for (int i = 0; i < nums.size(); i++) {
        int x = nums[i];
        if (i > 0 && x != nums[i-1]) {
            // 上一个连续相同段结束，可以把上一段对应的前缀和添加到 cnt
            int s = sum;
            for (int j = 0; j < i - lastStart; j++) {
                cnt[s % k]++;
                s -= nums[i-1];
            }
            lastStart = i;
        }
        sum += x;
        ans += cnt[sum % k];
    }
    return ans;
}

int main() {
    vector<int> nums = {1, 2, 3};
    int k = 3;
    long long result = numGoodSubarrays(nums, k);
    cout << result << endl;
    return0;
}