Hard

题目描述

给你一个按非递减顺序排列的整数数组 nums 和一个正整数 k。

如果 nums 的一个子数组的元素和能被 k 整除，则该子数组是好的。

返回 nums 中不同好子数组的数量。

如果子数组的值序列不同，则子数组是不同的。例如，在 [1, 1, 1] 中有 3 个不同的子数组，即 [1]、[1, 1] 和 [1, 1, 1]。

示例 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。

示例 2：

输入: nums = [2,2,2,2,2,2], k = 6
输出: 2
解释: 好子数组有 [2, 2, 2] 和 [2, 2, 2, 2, 2, 2]。例如，[2, 2, 2] 是好的，因为其元素和为 2 + 2 + 2 = 6，而 6 % k = 6 % 6 = 0。
注意 [2, 2, 2] 只被计算一次。

约束条件：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • nums 按非递减顺序排列
  • 1 <= k <= 10^9

解题思路

这道题的关键在于理解"不同子数组"的含义：只要子数组的值序列不同，就算作不同的子数组。

核心思路：

  1. 分类讨论：将子数组分为两类：

    • 单值子数组：所有元素都相等
    • 多值子数组：包含至少两个不同的值

  2. 单值子数组处理：

    • 将数组分割为连续相等元素的段
    • 对于每个段，如果值为val且长度为L，检查包含i个元素的子数组和i*val是否能被k整除
    • 对于每个满足条件的长度，该段贡献L-i+1个子数组

  3. 多值子数组处理：

    • 由于数组有序，任何包含多个不同值的子数组都有唯一的"严格递增边界"
    • 使用前缀和技巧：两个位置的前缀和模k相等，说明它们之间的子数组和能被k整除
    • 为避免重复计算单值子数组，只考虑跨越不同值的子数组

  4. 实现细节：

    • 预处理每个位置对应的段编号
    • 用哈希表记录每个前缀和模值在每个段中最后出现的位置
    • 遍历时累计跨段的贡献

时间复杂度优化：通过段的概念避免了暴力枚举，将复杂度从O(n²)降低到O(n)。

代码实现

class Solution {
public:
    long long numGoodSubarrays(vector<int>& nums, int k) {
        int n = nums.size();
        vector<int> segment(n);
        vector<int> segmentStart;
        
        // 找到每个连续相等段
        int seg = 0;
        segmentStart.push_back(0);
        for (int i = 0; i < n; i++) {
            segment[i] = seg;
            if (i + 1 < n && nums[i] != nums[i + 1]) {
                seg++;
                segmentStart.push_back(i + 1);
            }
        }
        segmentStart.push_back(n);
        
        long long result = 0;
        
        // 单值子数组
        for (int s = 0; s <= seg; s++) {
            int start = segmentStart[s];
            int end = segmentStart[s + 1];
            int len = end - start;
            long long val = nums[start];
            
            for (int i = 1; i <= len; i++) {
                if ((1LL * i * val) % k == 0) {
                    result += len - i + 1;
                }
            }
        }
        
        // 多值子数组
        unordered_map<int, vector<int>> lastPos;
        vector<long long> prefix(n + 1, 0);
        
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        lastPos[0].resize(seg + 2, -1);
        
        for (int i = 0; i < n; i++) {
            int mod = (int)(prefix[i + 1] % k);
            
            if (lastPos.find(mod) == lastPos.end()) {
                lastPos[mod].resize(seg + 2, -1);
            }
            
            for (int s = 0; s < segment[i]; s++) {
                if (lastPos[mod][s] != -1) {
                    result++;
                }
            }
            
            lastPos[mod][segment[i]] = i;
        }
        
        return result;
    }
};

class Solution:
    def numGoodSubarrays(self, nums: List[int], k: int) -> int:
        n = len(nums)
        segment = [0] * n
        segment_start = [0]
        
        # 找到每个连续相等段
        seg = 0
        for i in range(n):
            segment[i] = seg
            if i + 1 < n and nums[i] != nums[i + 1]:
                seg += 1
                segment_start.append(i + 1)
        segment_start.append(n)
        
        result = 0
        
        # 单值子数组
        for s in range(seg + 1):
            start = segment_start[s]
            end = segment_start[s + 1]
            length = end - start
            val = nums[start]
            
            for i in range(1, length + 1):
                if (i * val) % k == 0:
                    result += length - i + 1
        
        # 多值子数组
        last_pos = {}
        prefix = [0] * (n + 1)
        
        for i in range(n):
            prefix[i + 1] = prefix[i] + nums[i]
        
        last_pos[0] = [-1] * (seg + 2)
        
        for i in range(n):
            mod = prefix[i + 1] % k
            
            if mod not in last_pos:
                last_pos[mod] = [-1] * (seg + 2)
            
            for s in range(segment[i]):
                if last_pos[mod][s] != -1:
                    result += 1
            
            last_pos[mod][segment[i]] = i
        
        return result

public class Solution {
    public long NumGoodSubarrays(int[] nums, int k) {
        int n = nums.Length;
        int[] segment = new int[n];
        List<int> segmentStart = new List<int> { 0 };
        
        // 找到每个连续相等段
        int seg = 0;
        for (int i = 0; i < n; i++) {
            segment[i] = seg;
            if (i + 1 < n && nums[i] != nums[i + 1]) {
                seg++;
                segmentStart.Add(i + 1);
            }
        }
        segmentStart.Add(n);
        
        long result = 0;
        
        // 单值子数组
        for (int s = 0; s <= seg; s++) {
            int start = segmentStart[s];
            int end = segmentStart[s + 1];
            int length = end - start;
            long val = nums[start];
            
            for (int i = 1; i <= length; i++) {
                if ((long)i * val % k == 0) {
                    result += length - i + 1;
                }
            }
        }
        
        // 多值子数组
        Dictionary<int, int[]> lastPos = new Dictionary<int, int[]>();
        long[] prefix = new long[n + 1];
        
        for (int i = 0; i < n; i++) {
            prefix[i + 1] = prefix[i] + nums[i];
        }
        
        lastPos[0] = new int[seg + 2];
        Array.Fill(lastPos[0], -1);
        
        for (int i = 0; i < n; i++) {
            int mod = (int)(prefix[i + 1] % k);
            
            if (!lastPos.ContainsKey(mod)) {
                lastPos[mod] = new int[seg + 2];
                Array.Fill(lastPos[mod], -1);
            }
            
            for (int s = 0; s < segment[i]; s++) {
                if (lastPos[mod][s] != -1) {
                    result++;
                }
            }
            
            lastPos[mod][segment[i]] = i;
        }
        
        return result;
    }
}

var numGoodSubarrays = function(nums, k) {
    const n = nums.length;
    const distinctSubarrays = new Set();
    
    for (let i = 0; i < n; i++) {
        let sum = 0;
        for (let j = i; j < n; j++) {
            sum += nums[j];
            if (sum % k === 0) {
                const subarray = nums.slice(i, j + 1);
                distinctSubarrays.add(JSON.stringify(subarray));
            }
        }
    }
    
    return distinctSubarrays.size;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型大小
时间复杂度O(n × L_max)，其中 n 是数组长度，L_max 是最长连续相等段的长度
空间复杂度O(n + S × k)，其中 S 是段的数量，k 是取模后的可能值数量