题目链接：992. K 个不同整数的子数组（困难）

👉对应力扣题解

算法原理：

解法：滑动窗口

与模板题高度相似👇

C.滑动窗口-求子数组个数-恰好型滑动窗口——930. 和相同的二元子数组（模板题）

解法一：两个至多相减（ret+=right-left+1型）

击败14.14%

时间复杂度O(N)

解法二：两个至少相减（ret+=left型）

击败14.14%

时间复杂度O(N)

Java代码：

class Solution {
    //解法一：两个至多相减（ret+=right-left+1型）
    public int subarraysWithKDistinct(int[] nums, int k) {
        return solve(nums,k)-solve(nums,k-1);
    }
    private int solve(int[] nums,int k){
        int ret=0;
        Map<Integer,Integer> hash=new HashMap<>();
        for(int left=0,right=0;right<nums.length;right++){
            //进窗口
            hash.put(nums[right],hash.getOrDefault(nums[right],0)+1);
            //出窗口
            while(hash.keySet().size()>k){
                hash.put(nums[left],hash.get(nums[left])-1);
                if(hash.get(nums[left])==0) hash.remove(nums[left]);
                left++;
            }
            //更新
            ret+=right-left+1;
        }
        return ret;
    }
}

class Solution {
    //解法二：两个至少相减（ret+=left型）
    public int subarraysWithKDistinct(int[] nums, int k) {
        return solve(nums,k)-solve(nums,k+1);
    }
    private int solve(int[] nums,int k){
        int ret=0;
        Map<Integer,Integer> hash=new HashMap<>();
        for(int left=0,right=0;right<nums.length;right++){
            //进窗口
            hash.put(nums[right],hash.getOrDefault(nums[right],0)+1);
            //出窗口
            while(hash.keySet().size()==k){
                hash.put(nums[left],hash.get(nums[left])-1);
                if(hash.get(nums[left])==0) hash.remove(nums[left]);
                left++;
            }
            //更新
            ret+=left;
        }
        return ret;
    }
}