What is the approach to solving Subarrays with K Different Integers?

The optimal approach is to use a sliding window along with a hash map to count subarrays with at most k distinct integers and subtract subarrays with fewer than k distinct integers.

How can I improve the time complexity for Subarrays with K Different Integers?

The time complexity is optimized to O(n) using a sliding window approach with hash lookups, ensuring the algorithm only passes through the array a limited number of times.

What are the common mistakes when solving Subarrays with K Different Integers?

Common mistakes include failing to adjust the window properly when the number of distinct integers exceeds k or trying a brute-force solution that leads to O(n^2) complexity.

How do sliding windows and hash maps help with Subarrays with K Different Integers?

Sliding windows and hash maps allow for efficient counting of distinct integers within subarrays, enabling the solution to operate in linear time while minimizing unnecessary recalculations.

Can I apply this technique to similar problems?

Yes, this sliding window approach with hash maps is useful for problems that require counting distinct elements within subarrays or subranges, including variations with negative numbers or rotated arrays.

#992

Hard

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

K 个不同整数的子数组

给定一个正整数数组 nums 和一个整数 k ，返回 nums 中「好子数组」的数目。如果 nums 的某个子数组中不同整数的个数恰好为 k ，则称 nums 的这个连续、不一定不同的子数组为「好子数组」。例如， [1,2,3,1,2] 中有 3 个不同的整数： 1 ， 2 ，以及…

数组哈希表滑动窗口计数

题目描述

给定一个正整数数组 nums和一个整数 k，返回 nums 中「好子数组」 的数目。

如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为「好子数组」。

例如，[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。

子数组 是数组的连续部分。

示例 1：

输入：nums = [1,2,1,2,3], k = 2
输出：7
解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].

示例 2：

输入：nums = [1,2,1,3,4], k = 3
输出：3
解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].

提示：

1 <= nums.length <= 2 * 10⁴
1 <= nums[i], k <= nums.length

lightbulb

解题思路

方法一：双指针

我们遍历数组 $nums$ ，对于每个 $i$ ，我们需要找到最小的 $j_1$ ，使得 $nums[j_1], nums[j_1 + 1], \dots, nums[i]$ 中不同的整数个数小于等于 $k$ ，以及最小的 $j_2$ ，使得 $nums[j_2], nums[j_2 + 1], \dots, nums[i]$ 中不同的整数个数小于等于 $k-1$ 。那么 $j_2 - j_1$ 就是以 $i$ 结尾的满足条件的子数组的个数。

在实现上，我们定义一个函数 $f(k)$ ，表示 $nums$ 中每个位置 $i$ 对应的最小的 $j$ ，使得 $nums[j], nums[j + 1], \dots, nums[i]$ 中不同的整数个数小于等于 $k$ 。该函数可以通过双指针实现，具体实现见代码。

然后我们调用 $f(k)$ 和 $f(k-1)$ ，计算出每个位置对应的 $j_1$ 和 $j_2$ ，然后计算出以每个位置 $i$ 结尾的满足条件的子数组的个数，最后求和即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $nums$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

class Solution:
    def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
        def f(k):
            pos = [0] * len(nums)
            cnt = Counter()
            j = 0
            for i, x in enumerate(nums):
                cnt[x] += 1
                while len(cnt) > k:
                    cnt[nums[j]] -= 1
                    if cnt[nums[j]] == 0:
                        cnt.pop(nums[j])
                    j += 1
                pos[i] = j
            return pos

        return sum(a - b for a, b in zip(f(k - 1), f(k)))

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Candidate efficiently uses sliding window and hash map for optimal subarray counting.
question_mark
Understanding of counting subarrays with at most k distinct integers and leveraging this for exactly k.
question_mark
Candidate implements efficient window size adjustments without unnecessary operations.

warning

常见陷阱

外企场景

error
Failure to correctly adjust the window size when encountering more than k distinct integers.
error
Mistaking the problem for one requiring brute-force enumeration of all subarrays, leading to a time complexity of O(n^2).
error
Inaccurate handling of the edge case when the array contains fewer than k distinct integers.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Subarrays with at most k distinct integers.
arrow_right_alt
Count subarrays where the number of distinct integers is exactly k, but with negative integers.
arrow_right_alt
Subarrays with k distinct integers in a rotated array.

help

常见问题

外企场景

继续练习

#594 最长和谐子序列 #1010 总持续时间可被 60 整除的歌曲 #930 和相同的二元子数组