【滑动窗口】leetcode992. Subarrays with K Different Integers

992. Subarrays with K Different Integers

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A good array is an array where the number of different integers in that array is exactly k.

For example, [1,2,3,1,2] has 3 different integers: 1, 2, and 3.
A subarray is a contiguous（连续的） part of an array.

题意:求连续子数组中数个数为k的区间总数

思路：滑动窗口

首先，可以枚举区间的右端点，求出每个右端点的区间个数后相加就是结果。

设j1是区间[j1,i]中数的种类为k的最左边的端点。

设j2是区间[j2,i]中数的种类为k-1的最左边的端点。

那么符号条件的区间就是j2-j1。

(特判：当j走到0，区间中数的种类数还是小于k时，此时j1j2重合j2-j1为0，符合题意）

可以证明，当i向右走时，j不能往回走，所以可以使用滑动窗口求解。

使用哈希表记录，区间中数的种类。哈希表的增删改查为o(1)

时间复杂度O(N)。

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
    Map<Integer,Integer>S1=new HashMap<>();
    Map<Integer,Integer>S2=new HashMap<>();
    int res=0;

    for(int i=0,j1=0,j2=0,cnt1=0,cnt2=0;i<nums.length;i++){
        if(S1.getOrDefault(nums[i],0)==0)cnt1++;
        S1.put(nums[i],S1.getOrDefault(nums[i],0)+1);
        while(cnt1>k){
            S1.put(nums[j1],S1.getOrDefault(nums[j1],0)-1);
            if(S1.get(nums[j1])==0)cnt1--;
            j1++;
        }
        if(S2.getOrDefault(nums[i],0)==0)cnt2++;
        S2.put(nums[i],S2.getOrDefault(nums[i],0)+1);
        while(cnt2>=k){
            S2.put(nums[j2],S2.getOrDefault(nums[j2],0)-1);
            if(S2.get(nums[j2])==0)cnt2--;
            j2++;
        }
        res+=j2-j1;
    }
    return res;
    }
}