如何优化判断整数是否属于指定递归数列的Python代码

首先明确该数列的核心特性：从f(0)开始严格单调递增，所有项均为非负整数，不需要预生成固定长度的序列，也不需要存储所有历史项，按需生成+哈希集合查询即可解决你提到的耗时、硬编码、内存浪费问题。

优化思路 #

• 抛弃硬编码的步长生成逻辑，每次仅生成到大于当前待校验值为止
• 用集合存储已生成的数列项，查询时间复杂度为O(1)，远优于原代码列表查询的O(n)
• 仅保留最新的两个数列项用于生成下一项，不需要额外存储全量历史
• 提前过滤负数：数列所有项都是非负的，输入负数直接判定不属于数列
• 消除全局变量，逻辑封装更合理

完整实现代码 #

def is_all_in_series(input_list):
    # 初始项，集合用于O(1)查询，a、b分别保存f(n-2)、f(n-1)用于生成下一项
    series_set = {0, 1}
    a, b = 0, 1
    
    for num in input_list:
        # 负数直接不匹配
        if num < 0:
            return False
        # 已经生成过的项直接校验
        if num in series_set:
            continue
        # 待校验值大于当前最大项，按需生成直到超过待校验值
        while num > b:
            next_val = 9 * b - 7 * a
            series_set.add(next_val)
            a, b = b, next_val
        # 生成完还是不在集合里，说明不匹配
        if num not in series_set:
            return False
    # 所有项都匹配
    return True

# 输入处理逻辑修正
if __name__ == "__main__":
    length = int(input("Enter the length of input list: "))
    lst = []
    for _ in range(length):
        lst.append(int(input("Enter element: ")))
    result = "found" if is_all_in_series(lst) else "Not Found"
    print(result)

方案优势 #

• 内存占用极低：集合仅存实际生成过的数列项，不会预生成冗余项，无多余内存浪费
• 计算效率高：无多余重复计算，每次生成都是必要操作，集合查询无额外开销
• 无硬编码逻辑：不管是第100项还是第1000项，都会自动按需生成，不需要修改任何参数
• 修复了原代码的输入逻辑bug：原代码遍历未初始化的lst又追加元素，完全无法正常获取输入

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