在Julia中从Vector提取长度≥3的等差数列的高效方法

核心思路 #

针对大型向量，要避免冗余迭代和过高内存占用，最优路径是先对向量去重排序（等差数列在排序后必然是连续子序列），再通过一次线性遍历识别所有符合条件的序列。

代码实现 #

function extract_arithmetic_sequences(v::Vector{Int64})
    # 去重+排序，消除冗余数据，同时将等差数列转化为连续子序列
    sorted_unique = sort(unique(v))
    len = length(sorted_unique)
    len < 3 && return Vector{Vector{Int64}}()
    
    sequences = Vector{Vector{Int64}}()
    start_pos = 1
    current_diff = sorted_unique[2] - sorted_unique[1]
    
    for i in 3:len
        curr_diff = sorted_unique[i] - sorted_unique[i-1]
        if curr_diff != current_diff
            # 检查当前段长度是否达标
            if i - start_pos >= 3
                push!(sequences, sorted_unique[start_pos:i-1])
            end
            start_pos = i-1
            current_diff = curr_diff
        end
    end
    # 处理遍历结束后剩余的最后一段序列
    if len - start_pos + 1 >= 3
        push!(sequences, sorted_unique[start_pos:end])
    end
    
    return sequences
end

# 测试示例输入
input_vec = [1, 4, 5, 3, 9, 21, 16, 2, 22, 54, 17, 23]
result = extract_arithmetic_sequences(input_vec)
println(result)  # 输出 [[1, 2, 3, 4, 5], [21, 22, 23]]

效率说明 #

• 去重排序阶段：依赖Julia内置的高效排序算法，时间复杂度为O(n log n)，这是处理此类问题的必要基础开销。
• 线性遍历阶段：仅通过记录起始位置和当前公差完成识别，时间复杂度O(n)，内存占用极低，仅需存储结果序列和少量状态变量。
• 完全避免嵌套迭代，不会出现你之前遇到的内存溢出问题。

特殊情况说明 #

如果你的需求是寻找原向量中的连续子序列（而非所有元素组成的等差数列），原示例输入中不存在符合条件的结果，但可以用类似线性遍历的方式实现：

function extract_consecutive_arithmetic_subsequences(v::Vector{Int64})
    len = length(v)
    len < 3 && return Vector{Vector{Int64}}()
    
    sequences = Vector{Vector{Int64}}()
    start_pos = 1
    current_diff = v[2] - v[1]
    
    for i in 3:len
        curr_diff = v[i] - v[i-1]
        if curr_diff != current_diff
            if i - start_pos >= 3
                push!(sequences, v[start_pos:i-1])
            end
            start_pos = i-1
            current_diff = curr_diff
        end
    end
    if len - start_pos + 1 >= 3
        push!(sequences, v[start_pos:end])
    end
    
    return sequences
end

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