如何高效求解包含数组全部元素的最短连续子数组长度

当然存在，你可以用**滑动窗口（双指针）**算法实现，时间复杂度仅为O(n)，空间复杂度为O(k)（k为数组去重后的元素总数），远优于暴力的O(n²)解法。

核心思路 #

这个问题属于经典的「最小覆盖子串」变种，核心逻辑是用左右两个指针动态维护窗口范围，在保证窗口始终包含所有目标元素的前提下，尽可能缩小窗口长度，遍历一次数组就能得到结果：

• 第一步：先遍历一次原数组，统计所有去重后的元素，记总共有m个（本例中m=5）
• 第二步：初始化左指针left=0，用哈希表记录当前窗口内各元素的出现次数，用变量valid记录当前窗口已覆盖的不同目标元素数量
• 第三步：遍历右指针right扩展窗口，每次将A[right]加入统计：
  • 如果该元素的计数从0变为1，说明新增覆盖了一个目标元素，valid +=1
  • 当valid == m时，说明当前窗口已经覆盖所有目标元素，此时尝试收缩左指针找最小窗口：
    • 每次收缩前先计算当前窗口长度，更新全局最小长度
    • 将A[left]从计数中减去，如果减完后计数变为0，说明窗口不再覆盖该元素，valid -=1，停止收缩，继续移动右指针

代码示例（Python） #

def min_subarray_length(A):
    from collections import defaultdict
    # 统计目标元素集合
    target = set(A)
    m = len(target)
    count = defaultdict(int)
    valid = 0
    left = 0
    min_len = float('inf')
    
    for right in range(len(A)):
        num = A[right]
        if num in target:
            count[num] += 1
            if count[num] == 1:
                valid += 1
        # 窗口满足条件时收缩左边界
        while valid == m:
            # 更新最小长度
            current_len = right - left + 1
            if current_len < min_len:
                min_len = current_len
            # 移出左边界元素
            left_num = A[left]
            if left_num in target:
                count[left_num] -= 1
                if count[left_num] == 0:
                    valid -= 1
            left += 1
    return min_len

# 测试用例
A = [7,3,7,3,1,2,3,4,1]
print(min_subarray_length(A)) # 输出6

正确性验证 #

针对你给出的示例数组，算法运行过程中会找到右边界在索引7（元素为4）时，收缩左边界到索引2（元素为7），此时窗口范围是索引2到7，元素为[7,3,1,2,3,4]，长度为6，就是符合要求的最短子序列。

内容的提问来源于stack exchange，提问作者rohit