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

Categories:

题目描述
思路分析
1. 解法一：至多 K 个不同数（推荐）
相似题目

题目描述

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

思路分析

解法一：至多 K 个不同数（推荐）

核心思路：

计算 atMost(k)：至多包含 k 种整数的子数组数量。

目标答案为 atMost(k) - atMost(k-1)。

滑动窗口维护不同整数计数。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(k)。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int subarraysWithKDistinct(int[] nums, int k) {
        return atMost(nums, k) - atMost(nums, k - 1);
    }

    private int atMost(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        int left = 0;
        int res = 0;

        for (int right = 0; right < nums.length; right++) {
            count.put(nums[right], count.getOrDefault(nums[right], 0) + 1);
            while (count.size() > k) {
                count.put(nums[left], count.get(nums[left]) - 1);
                if (count.get(nums[left]) == 0) {
                    count.remove(nums[left]);
                }
                left++;
            }
            res += right - left + 1;
        }

        return res;
    }
}

func subarraysWithKDistinct(nums []int, k int) int {
	return atMost(nums, k) - atMost(nums, k-1)
}

func atMost(nums []int, k int) int {
	count := make(map[int]int)
	left := 0
	res := 0

	for right, val := range nums {
		count[val]++
		for len(count) > k {
			count[nums[left]]--
			if count[nums[left]] == 0 {
				delete(count, nums[left])
			}
			left++
		}
		res += right - left + 1
	}

	return res
}

相似题目

题目	难度	考察点
904. 水果成篮	中等	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口
340. 至多包含 K 个不同字符的最长子串	困难	滑动窗口
1004. 最大连续1的个数 III	中等	滑动窗口
992. K 个不同整数的子数组	困难	滑动窗口

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/87604932