多数组跨数组连续数字高效查找方案问询

原代码用itertools.product枚举所有组合，本质是暴力穷举，当子数组长度较大时，组合数会呈指数级增长（比如3个各含1000元素的子数组，会产生10亿次循环），效率极低。下面是针对性的优化方案：

核心思路 #

我们要找的序列是从第i个子数组取元素x+i（i从0开始），即序列为[x, x+1, x+2, ..., x+n-1]，其中n是子数组的总数。基于这个规律，我们可以：

1. 把每个子数组转换为集合，利用集合O(1)的成员查询速度替代列表O(k)的查询。
2. 选择长度最短的子数组作为遍历起点（减少循环次数），对其中每个元素x，依次验证x+i是否存在于第i个子数组对应的集合中。

优化后代码 #

def find_continuous_items(data):
    if not data:
        return
    # 处理只有一个子数组的情况：所有元素都是符合要求的序列
    if len(data) == 1:
        yield from ((item,) for item in data[0])
        return
    
    # 将每个子数组转为集合
    sets = [set(arr) for arr in data]
    n = len(data)
    
    # 选择长度最短的子数组作为遍历起点，减少循环次数
    min_len_idx = min(range(n), key=lambda i: len(data[i]))
    base_arr = data[min_len_idx]
    
    for x in base_arr:
        valid = True
        result = []
        for i in range(n):
            target = x + (i - min_len_idx)
            if target not in sets[i]:
                valid = False
                break
            result.append(target)
        if valid:
            yield tuple(result)

代码说明 #

• 边界处理：空输入直接返回；单个子数组时，每个元素自身就是符合要求的连续序列。
• 集合转换：把每个子数组转成集合，大幅降低成员查询的时间成本。
• 最优遍历起点：选择最短的子数组遍历，比如如果某个子数组只有10个元素，另一个有1000个，遍历10个的那个能减少90%以上的循环次数。
• 验证逻辑：对每个起始元素x，计算对应位置的目标值，检查是否在对应子数组的集合中，全部通过则返回该序列。

测试示例 #

用你给出的输入[[0, 5, 6, 11], [8, 9, 12], [7, 10, 13]]测试：

• 最短子数组是第二个和第三个（长度3），比如选第二个子数组遍历：
  • 8：检查8-1=7是否在第一个数组？不在，跳过。
    -9：检查9-1=8是否在第一个数组？不在，跳过。
    -12：检查12-1=11在第一个数组，12+1=13在第三个数组，所以序列(11,12,13)会被yield出来。

效率对比 #

假设3个子数组各有1000个元素，原代码需要执行1e9次循环，优化后的代码最多执行1000次循环，效率提升了100万倍以上。

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