滑动窗口实现「统计最大元素出现至少K次子数组数」报错求助

思路 #

直接统计合法子数组容易遗漏，换个更清晰的思路：用总子数组数减去不合法子数组数（即最大元素出现次数不足k次的子数组数）。

• 总子数组数可通过公式 n*(n+1)//2 快速计算（n为数组长度）；
• 不合法子数组数用滑动窗口统计：维护窗口[left, right]，保证窗口内最大元素出现次数<k，对每个右边界right，计算以它结尾的不合法子数组数量并累加。

代码实现（Python） #

def count_subarrays(nums, k):
    max_val = max(nums)
    n = len(nums)
    total = n * (n + 1) // 2
    left = 0
    count_max = 0
    invalid = 0
    
    for right in range(n):
        if nums[right] == max_val:
            count_max += 1
        
        # 窗口内最大元素次数达标时，收缩左边界直到次数不足k
        while count_max >= k:
            if nums[left] == max_val:
                count_max -= 1
            left += 1
        
        # 累加当前右边界对应的不合法子数组数量
        invalid += right - left + 1
    
    return total - invalid

测试用例验证 #

以nums=[1,3,2,3,3]，k=2为例：

1. 总子数组数：5*6//2=15
2. 统计不合法子数组数：
   • 右边界0：不合法数量1 → 累计1
   • 右边界1：不合法数量2 → 累计3
   • 右边界2：不合法数量3 → 累计6
   • 右边界3：收缩左边界到2，不合法数量2 → 累计8
   • 右边界4：收缩左边界到4，不合法数量1 → 累计9
3. 合法子数组数：15-9=6，与预期结果一致。

原错误思路的问题 #

你之前的滑动窗口逻辑仅在窗口满足条件时累加单个结果，既没有覆盖所有以当前右边界结尾的合法子数组，也未正确处理窗口收缩后的统计逻辑，导致漏算大部分合法情况。

内容的提问来源于stack exchange，提问作者Karina