Java 中具有 K 个不同数字的最小子数组

我们得到一个包含整数的数组。此外，还给出了一个整数 k。我们的任务是找到一个由最小范围 [lft, rght]（lft 和 rght 都包含在范围内）组成的数组，使得该范围内恰好有 k 个不同的数字。如果无法在给定的输入数组中找到 k 个不同的元素，则应在控制台上显示适当的消息。请观察以下示例。

示例 1

输入

arr[] = { 11, 11, 11, 12, 12, 13, 13, 14, 15, 17 }, k = 4

输出 {6, 9}

解释：范围 [6, 9] 包含四个不同的元素。此外，该窗口大小或范围大小是最小的。

示例 2

输入

arr[] = { 11, 12, 12, 13}, k = 3

输出 {0, 3}

解释：范围 [0, 3] 包含三个不同的元素。此外，该窗口大小或范围大小是最小的。

示例 3

输入

arr[] = { 11, 12, 12, 12, 13, 13}, k = 5

输出：无法在输入数组 arr[] 中找到五个不同的元素。

解释：输入数组只包含三个不同的元素。因此，不可能找到五个不同的元素。

朴素方法

该问题的朴素方法是找出所有子数组，然后检查子数组是否为 k 的大小。但是，有几点需要考虑。

算法

步骤 1：将提供的输入数组的每个元素作为所需子数组的起始元素 [第 j 个元素]。

步骤 2：在每次迭代中，创建一个空集来存储唯一的子数组元素。

• 从输入数组中选择剩余的每个元素 [j, j + 1, … n - 1] 作为最后一个元素 [第 k 个元素]。
• 将当前元素插入集合中。
• 如果集合大小为 k，则退出内循环并更新结果（已找到 k 个唯一元素，增加子数组大小有两种可能性：要么找到更多唯一元素，要么增加包含重复元素且应避免在所需结果中包含的子数组的大小）。

步骤 3：如果 (k == n)，则意味着没有找到从第 j 个索引开始的任何所需子数组。因此，应终止外循环。

步骤 4：显示找到的输出（如果找到）。否则，应在控制台上打印适当的消息。

实施

让我们来实现上述步骤。请观察以下程序。

文件名：SmallestSubarray.java

输出

For the input array: 
11 11 11 12 12 13 13 14 15 17 
The smallest subarray containing 4 distinct elements ranges from: [6, 9] 
 
For the input array: 
11 12 12 13 
The smallest subarray containing 3 distinct elements ranges from: [0, 3] 
 
For the input array: 
11 12 12 12 13 13 
The smallest subarray containing 5 distinct elements is not found.

复杂度分析：该程序使用嵌套 for 循环，使程序的时间复杂度为 O(n²)。此外，该程序使用哈希集，使程序空间复杂度为 O(n)，其中 n 是输入数组中存在的总元素数。

现在，我们将进行一些优化以降低时间和空间复杂度。

方法：滑动窗口

使用滑动窗口，我们可以降低程序的时间复杂度以及空间复杂度。但在编写程序之前，让我们看看实现结果所需的步骤。

步骤 1：创建一个地图来存储每个元素的出现次数。

步骤 2：取两个变量：st 和 ed，表示所需子数组的起始和结束位置。

步骤 3：在这里，我们将使用 j 和 k 作为窗口的起始点和结束点，并将 j = 0 和 k = 0。

步骤 4：遍历输入数组直到窗口的结束指针 (k) 到达输入数组的末尾。即，while( k < n) 执行以下操作

1. 将当前元素放入地图 mp[ inputArr[k] ]++ 并将 k 指向下一个索引
2. 检查窗口 [j, k - 1] 的大小是否等于 k。
3. 如果窗口大小小于 k，则继续。
4. 但是，如果窗口大小 (size == k)，则检查长度是否为所需的子数组。如果是，则更新变量 st 和 ed。
5. 之后，移动窗口，但要移动窗口，必须检查当前窗口的起始元素（即第 j 个元素）。如果第 j 个元素的频率为 1，则将其从地图中删除，否则将其频率减 1。

实施

让我们看看上述步骤的实现。

文件名：SmallestSubarray1.java

输出

For the input array: 
11 11 11 12 12 13 13 14 15 17 
The smallest subarray containing 4 distinct elements ranges from: [6, 9] 
 
For the input array: 
11 12 12 13 
The smallest subarray containing 3 distinct elements ranges from: [0, 3] 
 
For the input array: 
11 12 12 12 13 13 
The smallest subarray containing 5 distinct elements is not found.

复杂度分析：在最坏的情况下，元素最多只能添加或从哈希映射中删除一次。因此，程序的时间复杂度为 O(n)，其中 n 是输入数组中存在的总元素数。在最坏的情况下，哈希映射最多只能包含 k 个元素。因此，程序的空间复杂度为 O(k)。