题解 | #合法连续子段#

滑动窗口——java版
用两个指针表示窗口的左边界（i）和有边界（j），用map存储窗口中每个元素出现的次数，当窗口中的元素满足条件时，则从窗口的左边界到右边界之后的所有区间也都满足条件。
(i, j)
(i, j+1)
(i, j+2)
..........
(i, n -1)
区间数为 n - j 个 。 接着左指针右移，缩小区间，每移动一次，如果窗口仍然满足条件，则又会有 n - j 个合法区间。继续右移左指针，直到窗口不满足条件，再后移右指针去寻找下一个满足条件的窗口。

public class Main{
    public static void main(String[] args){
        Scanner cin = new Scanner(System.in);
        int n = cin.nextInt();
        int m = cin.nextInt();
        int[] a = new int[n];
        for(int i = 0; i < n; i++){
            a[i] = cin.nextInt();
        }
        
        Map<Integer, Integer> map = new HashMap<>();
        int i = 0;
        int j = 0;
        long count = 0;
        while(j < n && i <= j){
            int num = map.getOrDefault(a[j], 0) + 1;
            map.put(a[j], num);
            if(num == m){
                // 如果到j这里满足条件，那么所有j之后也都满足，直接计算有多少个区间
                count += n - j;
                // i向后移，直到区间不满足条件。每移动一次就会有新的合法区间
                while(i < j && map.get(a[i]) != num){
                    map.put(a[i], map.get(a[i]) - 1);
                    i++;
                    count += n - j;
                }
                if(map.get(a[i]) == num){
                    map.put(a[i], map.get(a[i]) - 1);
                    i++;
                }
            }
            j++;
        }
        System.out.println(count);
    }
}