2537.统计好子数组的数目

发表于： 分类于：
字数： 1160 阅读：≈ 3分钟

💫 2537.统计好子数组的数目

给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。

一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。

子数组 是原数组中一段连续 非空 的元素序列。

思路

基本思想

统计符合条件的子数组，第一个想法就是使用滑动窗口，每一个滑动窗口都是一个子数组，然后统计滑动窗口中元素的出现次数，当前元素有n个，则可以形成n*(n-1)/2对，滑动窗口不断累加，一旦超过k就得到了一个好数组，此时就开始缩小滑动窗口

缩小时有一定的讲究，每删除一个左边的元素，该元素形成的对数可能就会减小，举例来说，当前元素原本有7个，可以形成21对，减小之后变成6个，只能形成15对，删除一个元素后元素的对数减小了6对，也就是当前元素减小之后，使用pairs-=count更新对数即可：

1
2
3
4
5
6
7

while(pairs>=k){
    ++res;
    //减小当前窗户左边元素的出现次数，并且减小其对数
    count=map.get(nums[left]);
    map.put(nums[left++],--count);
    pairs-=count;
}

需要注意的是，一旦当前滑动窗口中的对数小于k就停止缩小，此时滑动窗口左边有left个元素，不管滑动窗口是否符合条件，加上这left个元素一定是符合要求的好子数组，因为处于left-1位置的元素是最后一个被删除的元素（临界点），加上他就满足了要求，这是临界点

举例来说，当前需要k=2对，原始数组为[3,1,4,3,2,2,4,5]。窗口中的元素为[3,2,2,4]，被删除的元素为[3,1,4]，则left=3，不管后面怎么变化只要向左带上被删除的元素4就可以形成一个好子数组，而有三种可以带上4的情况:[4],[1,4],[3,1,4]，所以每次都需要+left

执行流程

  1. 开始滑动窗口，每次统计元素出现次数以及当前窗口形成的元素对数
  2. 滑动窗口一变化，带上左边的元素就可以形成好子数组，所以每次都要+left
  3. 当前滑动窗口元素对数大于k就开始缩小窗口
  4. 缩小时需要减小元素的出现次数和当前元素形成的对数
  5. 滑动完毕返回答案

代码

根据以上分析，得出以下代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31

class Solution {
    //滑动窗口统计当前窗口中元素个数
    //然后判断当前窗口中元素有没有k对、
    //当前元素有n个，则可以形成n*(n-1)/2对
    private long res=0;
    public long countGood(int[] nums, int k) {
        Map<Integer,Integer>map=new HashMap<>();
        long res=0;
        //滑动窗口，一旦有k对就开始缩小
        int pairs=0,left=0;
        for(int i=0;i<nums.length;++i){
            int count=map.getOrDefault(nums[i],0);
            map.put(nums[i],count+1);
            //元素对数增加count对
            pairs+=count;
            //left在不满足条件的窗口左边最小处（临界点）
            //前面的left个元素算上就满足了条件
            //每次都加上left，这样就不用每次都从头开始计算
            //这里是核心
            res+=left;
            while(pairs>=k){
                ++res;
                //减小当前窗户左边元素的出现次数，并且减小其对数
                count=map.get(nums[left]);
                map.put(nums[left++],--count);
                pairs-=count;
            }
        }
        return res;
    }
}

总结

核心就是滑动窗口缩小到刚好不满足条件时（临界点），此时不管后续滑动窗口怎么变化，加上删除的临界点就可以满足条件，于是每次都会形成满足条件的好子数组，也就是都需要+left