LeetCode 992. K 个不同整数的子数组

解题思路

举一个例子可能会比较好理解
nums = [1,2,1,2,3], k = 2
i表示的是右指针，j表示的是左指针。
i=3时，
需要求出符合子数组中含有k个不同整数，此时的j1=0
需要求出符合子数组中含有k-1个不同整数，此时的j2=1
j1~j2之间就是符合子数组中含有k个不同整数的子数组个数。

相关代码

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {  
        int a1[] = new int[20010];
        int a2[] = new int[20010];
        int res=0;
        for(int i=0,j1=0,j2=0,cnt1=0,cnt2=0;i<nums.length;i++){
            if(a1[nums[i]]==0) cnt1++;
            a1[nums[i]]++;
            while(j1<=i&&cnt1>k){
                if(a1[nums[j1]]==1) cnt1--;
                a1[nums[j1]]--;
                j1++;
            }

            if(a2[nums[i]]==0) cnt2++;
            a2[nums[i]]++;
            while(j2<=i&&cnt2>=k){
                if(a2[nums[j2]]==1) cnt2--;
                a2[nums[j2]]--;
                j2++;
            }
            if(cnt1==k&&cnt2==k-1){
                res=res+j2-j1;
            } 
        }
        return res;
    }
}