2023-02-20：小A认为如果在数组中有一个数出现了至少k次， 且这个数是该数组的众数，即出现次数最多的数之一， 那么这个数组被该数所支配， 显然当k比较大的时候，有些数组不被任何数所支配。 现在

2023-02-20：小A认为如果在数组中有一个数出现了至少k次，
且这个数是该数组的众数，即出现次数最多的数之一，
那么这个数组被该数所支配，
显然当k比较大的时候，有些数组不被任何数所支配。
现在小A拥有一个长度为n的数组，她想知道内部有多少个区间是被某个数支配的。
2 <= k <= n <= 100000，
1 <= 数组的值 <= n。
来自小红书。

答案2023-02-20：

窗口问题。
求总数，求不被支配的数量。
时间复杂度：O(N)。
空间复杂度：O(N)。

代码用rust编写。代码如下：

use rand::Rng;

use std::collections::HashMap;

use std::iter::repeat;

fn main() {

    let nn = 100;

    let test_times = 5000;

    println!("测试开始");

    for i in 0..test_times {

        let n = rand::thread_rng().gen_range(0, nn) + 1;

        let mut arr = random_array(n);

        let k = rand::thread_rng().gen_range(0, n) + 1;

        let ans1 = dominates1(&mut arr, k);

        let ans2 = dominates2(&mut arr, k);

        if ans1 != ans2 {

            println!("出错了!");

            return;

        }

    }

    println!("测试结束");

}

// 暴力方法

// 为了验证

// 时间复杂度O(N^3)

fn dominates1(arr: &mut Vec<i32>, k: i32) -> i32 {

    let n = arr.len() as i32;

    let mut ans = 0;

    for l in 0..n {

        for r in l..n {

            if ok(arr, l, r, k) {

                ans += 1;

            }

        }

    }

    return ans;

}

fn ok(arr: &mut Vec<i32>, l: i32, r: i32, k: i32) -> bool {

    let mut map: HashMap<i32, i32> = HashMap::new();

    for i in l..=r {

        if map.contains_key(&arr[i as usize]) {

            map.insert(arr[i as usize], map.get(&arr[i as usize]).unwrap() + 1);

        } else {

            map.insert(arr[i as usize], 1);

        }

    }

    for (_, times) in map.iter() {

        if *times >= k {

            return true;

        }

    }

    return false;

}

// 正式方法

// 时间复杂度O(N)

fn dominates2(arr: &mut Vec<i32>, k: i32) -> i32 {

    let n = arr.len() as i32;

    // 总数量

    let all = n * (n + 1) / 2;

    // 不被支配的区间数量

    let mut except = 0;

    // 次数表

    // 0 : 0

    // 1 : 0

    // 2 : 0

    let mut cnt: Vec<i32> = repeat(0).take((n + 1) as usize).collect();

    // l ... r

    // 窗口用这个形式[l,r)

    // l...r-1 r(x)

    // l == 0 r == 0 [l,r) 一个数也没有

    // l == 0 r == 1 [0..0]

    let mut l = 0;

    let mut r = 0;

    while l < n {

        // [r] 即将要进来的

        // cnt[arr[r]] + 1 < k

        while r < n && cnt[arr[r as usize] as usize] + 1 < k {

            // cnt[arr[r]]++;

            // r++

            cnt[arr[r as usize] as usize] += 1;

            r += 1;

        }

        // l..l

        // l..l+1

        // l..l+2

        // l..r-1

        except += r - l;

        cnt[arr[l as usize] as usize] -= 1;

        l += 1;

    }

    return all - except;

}

// 为了测试

fn random_array(n: i32) -> Vec<i32> {

    let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();

    for i in 0..n {

        ans[i as usize] = rand::thread_rng().gen_range(0, n) + 1;

    }

    return ans;

}

2023-02-20：小A认为如果在数组中有一个数出现了至少k次， 且这个数是该数组的众数，即出现次数最多的数之一， 那么这个数组被该数所支配， 显然当k比较大的时候，有些数组不被任何数所支配。 现在的相关教程结束。