如何优化求解元素差值不大于1的最长连续子数组的算法

问题描述 #

求解数组中元素最大值与最小值差值不超过1的最长连续子数组，例如输入数组为[1, 1, 2, 3, 4, 5]时，目标输出为[1,1,2]。

原有代码缺陷 #

你现有的实现采用暴力枚举所有长度的子数组的思路，每次校验子数组都要单独计算最大值和最小值，整体时间复杂度为O(n²)，当数组长度较大时运行速度会非常慢。

优化思路 #

采用滑动窗口（双指针）方法，利用「满足条件的子数组内最多只能有两种不同元素，且两种元素差值不超过1」的特性，将时间复杂度降到O(n)：

• 用左右两个指针标记当前校验窗口的边界
• 用字典记录窗口内所有元素的出现频率
• 右指针不断向右扩展，将新元素加入频率统计
• 当窗口内元素的最大最小值差值超过1时，向右移动左指针收缩窗口，直到窗口重新满足条件
• 遍历过程中记录最长满足条件的窗口的起止位置，最终返回对应子数组

优化后代码 #

def longest_subarray(arr):
    if not arr:
        return []
    left = 0
    max_length = 0
    window_start = 0
    freq_map = {}

    for right in range(len(arr)):
        current_num = arr[right]
        freq_map[current_num] = freq_map.get(current_num, 0) + 1

        # 收缩左边界直到窗口满足条件
        while max(freq_map.keys()) - min(freq_map.keys()) > 1:
            left_num = arr[left]
            freq_map[left_num] -= 1
            if freq_map[left_num] == 0:
                del freq_map[left_num]
            left += 1
        
        # 更新最长窗口记录
        current_window_len = right - left + 1
        if current_window_len > max_length:
            max_length = current_window_len
            window_start = left
    
    return arr[window_start: window_start + max_length]

测试验证 #

输入longest_subarray([1, 1, 2, 3, 4, 5])，输出结果为[1, 1, 2]，符合要求。

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