一、相关概念

二、题目

题目

思路

一开始用暴力求解法，时间复杂度是O（nnn），参考了大神的代码后是O（n）。人和人是有差距的啊。。。
滑动窗口

代码

import java.util.Arrays;
import java.util.Scanner;

public class 区间统计_滑动窗口 {

    public static void main(String[] args) {
        new 区间统计_滑动窗口().exe();
    }

    private void exe() {
        Scanner scan = new Scanner(System.in);
        // n个数字
        int n = scan.nextInt();
        // 区间长度为k
        int k = scan.nextInt();
        // 至少存在一个数出现了t次
        int t = scan.nextInt();
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = scan.nextInt();
        }
        System.out.println(Arrays.toString(arr));
        int r = process(arr, n, k, t);
        System.out.println(r);
    }

    private int process(int[] arr, int n, int k, int t) {
        if (k > n) {
            return 0;
        }
        // 满足条件的区间个数
        int num = 0;
        // 区间内每个数字出现的次数
        int[] showCount = new int[10005];
        // 滑动窗口
        int l = 0;
        int r = k - 1;
        // 区间内出现次数>=t的数字个数
        int count = 0;
        // 初始化showCount数组
        for (int i = l; i <= r; i++) {
            showCount[arr[i]]++;
            if (showCount[arr[i]] == t) {
                count++;
            }
        }
        if (count > 0) {
            num++;
        }
        // 滑动窗口
        l = l + 1;
        r = r + 1;
        while (l <= n - k) {
            showCount[arr[l - 1]]--;
            if (showCount[arr[l - 1]] == t - 1) {
                count--;
            }
            showCount[arr[r]]++;
            if (showCount[arr[r]] == t) {
                count++;
            }
            if (count > 0) {
                num++;
            }
            l++;
            r++;
        }
        return num;
    }

}

参考文献

牛客_美团9月6日后台开发 笔试 编程题