求线性时间复杂度的最长无重复值子数组算法及O(n²)解法优化咨询

嘿，我完全懂你现在的困扰——O(n²)的时间复杂度在处理大规模数组时肯定会力不从心，毕竟每次移动指针都要线性检查子数组里的重复元素，这太浪费时间了。咱们直接来搞个线性时间复杂度的解法，完美适配任意长度n的数组。

问题根源 #

你当前的方案里，check_dups函数每次都要遍历i到j的子数组，相当于外层指针移动时，内层还要做一次线性扫描，这就导致了整体O(n²)的时间开销。要优化的核心就是避免重复检查子数组，用更高效的方式追踪重复元素的位置。

最优解法：滑动窗口+哈希表 #

这个方法的核心是用两个指针维护一个「无重复元素的滑动窗口」，同时用哈希表（字典）记录每个元素最后出现的索引，这样就能在O(1)时间内判断当前元素是否在窗口内重复，并快速调整窗口的左边界。

具体步骤

• 初始化左指针left=0，记录最长子数组的长度max_length=0和起始索引start_index=0，再用一个字典last_seen存储元素到其最新索引的映射。
• 遍历右指针right从0到数组末尾：
  1. 如果当前元素arr[right]已经在last_seen里，并且它的最后出现位置在当前窗口内（即last_seen[arr[right]] >= left），就把左指针left移动到这个重复元素的下一个位置，确保窗口内没有重复。
  2. 更新last_seen中当前元素的索引为right。
  3. 计算当前窗口的长度，如果比max_length大，就更新max_length和start_index。
• 最后根据start_index和max_length截取最长无重复子数组。

代码实现

def longest_unique_subarray(arr):
    n = len(arr)
    last_seen = {}
    left = 0
    max_length = 0
    start_index = 0

    for right in range(n):
        # 如果当前元素在窗口内重复，调整左边界
        if arr[right] in last_seen and last_seen[arr[right]] >= left:
            left = last_seen[arr[right]] + 1
        
        # 更新当前元素的最新索引
        last_seen[arr[right]] = right
        
        # 更新最长子数组的信息
        current_length = right - left + 1
        if current_length > max_length:
            max_length = current_length
            start_index = left
    
    # 返回最长无重复子数组
    return arr[start_index:start_index + max_length]

# 测试你的示例数组
arr = [1, 4, 3, 2, 4, 2, 8, 1, 9]
print(longest_unique_subarray(arr))  # 输出: [4, 2, 8, 1, 9]

复杂度分析 #

• 时间复杂度：O(n)。每个元素最多被左指针和右指针各访问一次，没有嵌套的线性操作。
• 空间复杂度：O(k)，其中k是数组中不同元素的数量。最坏情况下（所有元素都不重复），空间复杂度是O(n)。

这个解法完美解决了你之前的性能问题，不管数组多长都能高效处理～

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