如何统计数组中所有元素至少出现两次的连续子数组数量？

这道题可以通过**滑动窗口（双指针）**的方法在O(n)时间复杂度内解决，核心思路如下：

• 我们需要统计所有满足「子数组内每个元素至少出现2次」的连续子数组，等价于统计子数组中「出现次数≥2的元素种类数」等于「子数组内不同元素总种类数」的子数组数量。
• 遍历数组固定右边界r，维护一个滑动窗口[l, r]，不断调整左边界l的位置，直到窗口[l, r]不再满足上述条件。此时所有左端点小于l的子数组[0..l-1, r]全部满足条件，直接累加l到结果即可。
• 遍历过程中维护两个计数变量：
  • distinct：当前窗口内不同元素的总种类数
  • valid：当前窗口内出现次数≥2的元素种类数

from collections import defaultdict

def count_valid_subarrays(arr):
    freq = defaultdict(int)
    distinct = 0  # 窗口内不同元素的数量
    valid = 0     # 窗口内出现次数≥2的元素数量
    l = 0
    res = 0
    for r in range(len(arr)):
        num = arr[r]
        if freq[num] == 0:
            distinct += 1
        freq[num] += 1
        if freq[num] == 2:
            valid += 1
        # 尝试右移左指针，直到窗口不满足条件
        while l <= r and distinct == valid:
            left_num = arr[l]
            freq[left_num] -= 1
            if freq[left_num] == 1:
                valid -= 1
            if freq[left_num] == 0:
                distinct -= 1
            l += 1
        # 所有<l的左端点对应的子数组都满足条件
        res += l
    return res

# 测试示例
print(count_valid_subarrays([0,0,0])) # 输出3
print(count_valid_subarrays([1,2,1,2,3])) # 输出1

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