求包含原字符串全部字符的最短子数组的首尾索引

问题描述 #

例如输入字符串abghjsag，需要找到包含所有不同字符的最短子数组，答案是6（对应子数组abghjs）。我已实现一个时间复杂度为O(n²)的算法，但不确定是否存在O(n)的解法，也未找到相关内容，以下是我的O(n²)实现：

def Subbaray(s):
    alphabet = set(s)
    substr = []
    for i in range(len(s)):
        for j in range(i, len(s)):
            substr.append((s[i:j+1], i, j+1))
    minlen = len(s)
    mini = 0
    minj = len(s)-1
    for subst in substr:
        if len(set(subst[0])) == len(alphabet):
            if len(subst[0]) < minlen:
                minlen = len(subst[0])
                mini = subst[1]
                minj = subst[2]            
    return mini, minj

O(n)复杂度解法：滑动窗口（双指针） #

这个问题属于最小覆盖子串的变种，完全可以用滑动窗口算法实现O(n)的时间复杂度，核心思路是通过左右指针动态调整窗口范围，在遍历一次字符串的过程中找到最优解。

实现思路

1. 统计字符串中所有不同字符的总数，记为unique_chars_count
2. 用哈希表char_count记录当前窗口内各字符的出现次数
3. 用left和right两个指针分别表示窗口的左、右边界，初始都为0
4. 用valid变量记录窗口中满足出现次数要求的字符数（这里只要出现至少1次就算满足）
5. 移动right指针扩展窗口，更新char_count和valid，直到valid等于unique_chars_count
6. 此时尝试移动left指针缩小窗口，同时更新最小窗口的起始位置和长度，直到valid小于unique_chars_count
7. 重复步骤5-6，直到right遍历完整个字符串

Python实现代码

def shortest_subarray_with_all_chars(s):
    if not s:
        return (0, 0)
    
    unique_chars = set(s)
    unique_count = len(unique_chars)
    char_count = {}
    left = 0
    valid = 0
    min_len = float('inf')
    result_left, result_right = 0, 0
    
    for right in range(len(s)):
        current_char = s[right]
        # 更新窗口内字符计数
        char_count[current_char] = char_count.get(current_char, 0) + 1
        # 如果当前字符刚满足至少出现一次，valid加1
        if char_count[current_char] == 1:
            valid += 1
        
        # 当窗口包含所有字符时，尝试缩小左边界
        while valid == unique_count:
            # 更新最小窗口信息
            current_window_len = right - left + 1
            if current_window_len < min_len:
                min_len = current_window_len
                result_left = left
                result_right = right + 1  # 保持和原函数返回的右边界一致（左闭右开）
            
            # 移动左指针，缩小窗口
            left_char = s[left]
            char_count[left_char] -= 1
            if char_count[left_char] == 0:
                valid -= 1
            left += 1
    
    return (result_left, result_right)

复杂度说明

• 时间复杂度：O(n)，每个字符最多被left和right指针各访问一次，整体遍历次数为线性
• 空间复杂度：O(k)，其中k是字符串中不同字符的数量，哈希表最多存储k个键值对

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