Microsoft OA 面试真题解析：最短含至少 K 个不同整数的子数组

For an array of n positive integers arr and an integer k, a subarray is considered good if it consists of at least k distinct integers. Find the minimum length subarray that is good. If there is no such subarray, return -1.

Example

arr = [2, 2, 1, 1, 3]
k = 3

The subarrays with at least k = 3 distinct integers are [2, 2, 1, 1, 3] and [2, 1, 1, 3]. Return 4, the minimum length of a good subarray.

Function Description

Complete the function findMinimumLengthSubarray in the editor below.

• INTEGER_ARRAY arr: the array to partition
• INTEGER k: the number of distinct elements a good subarray must contain

The function is expected to return an INTEGER.

这道题要求在数组中找到“包含至少 k 个不同整数”的最短连续子数组，典型做法是使用滑动窗口配合哈希表统计窗口内每个元素的出现次数。右指针不断扩展窗口，当不同元素数量达到 k 后，再移动左指针尽量缩短窗口，同时维护计数表，更新最小长度。若整个过程都无法凑出 k 个不同元素，则返回 -1。该题的核心是“扩张 + 收缩”的双指针思路，时间复杂度可做到 O(n)，适合处理大规模数组。