Medium

题目描述

给你一个整数数组 nums 和一个整数 k，返回 nums 中好子数组的数目。

如果一个子数组 arr 中至少有 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j]，则称 arr 是一个好子数组。

子数组是数组中一个连续的非空元素序列。

示例 1：

输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是数组 nums 本身。

示例 2：

输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。

提示：

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i], k <= 10^9

解题思路

这道题要求统计所有好子数组的数量，其中好子数组是指至少包含 k 对相等元素的子数组。

核心思路：

使用滑动窗口的思想来解决。对于每个左边界 left，我们找到最小的右边界 right，使得 [left, right] 区间内的相等对数至少为 k。一旦找到这样的 right，那么所有以 left 为左边界、右边界大于等于 right 的子数组都是好子数组。

算法步骤：

  1. 使用哈希表记录当前窗口内每个元素的出现次数
  2. 维护当前窗口内相等对的总数 pairs
  3. 对于每个左边界 left：
    • 扩展右边界 right，直到 pairs >= k
    • 此时以 left 为左边界的所有好子数组数量为 n - right
    • 收缩左边界，更新 pairs

关键点：

  • 当添加一个元素时，如果该元素已经出现了 count 次，那么新增的相等对数为 count
  • 当移除一个元素时，如果该元素还剩 count 次，那么减少的相等对数为 count

时间复杂度为 O(n)，空间复杂度为 O(n)。

代码实现

class Solution {
public:
    long long countGood(vector<int>& nums, int k) {
        int n = nums.size();
        unordered_map<int, int> count;
        long long pairs = 0;
        long long result = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            pairs += count[nums[right]];
            count[nums[right]]++;
            
            while (pairs >= k) {
                result += n - right;
                count[nums[left]]--;
                pairs -= count[nums[left]];
                left++;
            }
        }
        
        return result;
    }
};

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:
        from collections import defaultdict
        
        n = len(nums)
        count = defaultdict(int)
        pairs = 0
        result = 0
        left = 0
        
        for right in range(n):
            pairs += count[nums[right]]
            count[nums[right]] += 1
            
            while pairs >= k:
                result += n - right
                count[nums[left]] -= 1
                pairs -= count[nums[left]]
                left += 1
        
        return result

public class Solution {
    public long CountGood(int[] nums, int k) {
        int n = nums.Length;
        Dictionary<int, int> count = new Dictionary<int, int>();
        long pairs = 0;
        long result = 0;
        int left = 0;
        
        for (int right = 0; right < n; right++) {
            if (count.ContainsKey(nums[right])) {
                pairs += count[nums[right]];
                count[nums[right]]++;
            } else {
                count[nums[right]] = 1;
            }
            
            while (pairs >= k) {
                result += n - right;
                count[nums[left]]--;
                pairs -= count[nums[left]];
                left++;
            }
        }
        
        return result;
    }
}

var countGood = function(nums, k) {
    const n = nums.length;
    const count = new Map();
    let pairs = 0;
    let result = 0;
    let left = 0;
    
    for (let right = 0; right < n; right++) {
        pairs += count.get(nums[right]) || 0;
        count.set(nums[right], (count.get(nums[right]) || 0) + 1);
        
        while (pairs >= k) {
            result += n - right;
            count.set(nums[left], count.get(nums[left]) - 1);
            pairs -= count.get(nums[left]);
            left++;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型分析
时间复杂度O(n)，其中 n 是数组长度。每个元素最多被访问两次（一次作为右边界，一次作为左边界）
空间复杂度O(n)，哈希表存储元素频次，最坏情况下所有元素都不相同

相关题目