最长连续序列求解代码优化及面试解题技巧咨询

问题需求 #

找出数组中最长的连续数字序列（包含递增序列和递减序列），示例如下：

• 输入：[2,3,4,5,8,0]，输出：3,[2,3,4,5]
• 输入：[2,3,4,5,8,0,10,9,8,7,6,5]，输出：5,[10,9,8,7,6,5]
• 输入：[2,3,4,3,2,1]，输出：3,[4,3,2,1]

个人情况 #

面试中遇到该问题，花费了近50%的面试时间才完成，现提供自己编写的Python代码，希望得到代码优化方案，同时请教面试中快速解决此类算法问题的技巧。

本人编写的代码 #

l = [2,3,4,3,2,1]

flag1 = 0
flag2 = 0
index = 0
seq = 0
seq_dict = {}
n = len(l)
for i in range(n-1):
    
    if (l[i]+1 == l[i+1]):
        if (flag2 == 1):
            index = i
            seq_dict.update({seq: [index, flag1, flag2]})
            seq = 0
            flag2 = 0 
        elif(flag1 == 0 and i == n-2):
            index = i+1
            flag1 = 1
            seq += 1
            seq_dict.update({seq: [index, flag1, flag2]})   
        flag1 = 1 
        seq += 1
    
    elif (l[i]-1 == l[i+1]):
        if (flag1 == 1):
            index = i-1
            seq_dict.update({seq: [index, flag1, flag2]})
            seq = 0
            flag1 = 0
        elif(flag2 == 1 and i == n-2):
            index = i+1
            flag2 = 1
            seq += 1
            seq_dict.update({seq: [index, flag1, flag2]})  
        flag2 = 1
        seq += 1

    else:
        if(seq != 0 and (flag1 == 1 or flag2 == 1)):
            index = i
            seq_dict.update({seq: [index, flag1, flag2]})  
        seq = 0
        flag1 = 0
        flag2 = 0
        index = 0   

final = []

m = max(seq_dict)
print(m)
end = seq_dict[m][0]
while(m >= 0):
    final.append(l[end - m])
    m -= 1
print(final)

代码优化方案 #

原始代码逻辑冗余，依赖多flag和字典存储所有序列状态，易出错且可读性差。优化思路是一次遍历，实时跟踪当前序列的关键状态，同时记录最长序列信息，时间复杂度O(n)：

def longest_consecutive_sequence(arr):
    if not arr:
        return 0, []
    
    max_len = 1
    current_len = 1
    start_idx = 0
    max_start = 0
    # 0: 初始状态, 1: 递增, -1: 递减
    trend = 0

    for i in range(1, len(arr)):
        if arr[i] == arr[i-1] + 1:
            if trend == -1:
                # 从递减切换为递增，重置当前序列起始点
                current_len = 2
                start_idx = i-1
                trend = 1
            else:
                current_len += 1
                trend = 1
        elif arr[i] == arr[i-1] - 1:
            if trend == 1:
                # 从递增切换为递减，重置当前序列起始点
                current_len = 2
                start_idx = i-1
                trend = -1
            else:
                current_len += 1
                trend = -1
        else:
            # 序列中断，重置所有状态
            current_len = 1
            start_idx = i
            trend = 0
        
        # 更新最长序列记录
        if current_len > max_len:
            max_len = current_len
            max_start = start_idx
    
    # 示例中输出长度为元素个数减1（如4个元素的序列输出3）
    return max_len - 1, arr[max_start:max_start + max_len]

# 测试示例
print(longest_consecutive_sequence([2,3,4,5,8,0]))       # 输出 (3, [2, 3, 4, 5])
print(longest_consecutive_sequence([2,3,4,5,8,0,10,9,8,7,6,5]))  # 输出 (5, [10, 9, 8, 7, 6, 5])
print(longest_consecutive_sequence([2,3,4,3,2,1]))       # 输出 (3, [4, 3, 2, 1])

优化点说明：

1. 简化状态管理：用单个trend变量标记序列类型，替代多flag的混乱逻辑
2. 实时更新最长序列：遍历过程中直接维护最长序列的起始位置和长度，无需额外存储所有序列
3. 边界覆盖全面：处理了空数组、序列末尾结束、趋势切换等多种情况
4. 可读性提升：逻辑分支清晰，注释辅助理解，代码结构简洁

面试快速解决此类算法问题的技巧 #

1. 先确认问题细节：
   面试时先和面试官明确定义，比如这里的"长度"是元素个数还是元素个数减1，避免理解偏差浪费时间。
2. 从暴力解法过渡到优化：
   先想暴力思路（比如遍历每个元素向前后扩展），再思考如何通过一次遍历把时间复杂度降到O(n)，明确优化方向。
3. 用最少变量跟踪关键状态：
   对于连续子序列问题，只需跟踪当前序列的起始位置、长度、趋势（如果需要），以及全局最长序列的信息，不用存储所有可能的序列。
4. 先写伪代码框架：
   面试时先在白板/纸上写出核心逻辑框架，再填充细节：

   初始化最长长度、当前长度、起始位置
   遍历数组从第二个元素开始：
       判断当前元素与前一个的关系（递增/递减/无关）
       更新当前序列状态
       如果当前序列更长，更新最长序列信息
   返回最长序列的长度和子数组
   

5. 主动测试边界案例：
   提前考虑空数组、单元素数组、全递增/递减数组、序列在开头/结尾、趋势切换等情况，确保代码覆盖所有场景。
6. 优先保证代码简洁：
   不用复杂数据结构，能用简单变量解决的就不用字典、列表等，减少出错概率，也让面试官更容易理解你的思路。

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