是否有更简便的方法从三组数字中查找符合要求的等差数列？

核心逻辑 #

三个数a（来自第一组）、b（来自第二组）、c（来自第三组）构成等差数列的充要条件为 2*b = a + c，变形可得 c = 2*b - a。基于该推导可将原三重循环的O(nmk)时间复杂度降低到O(n*m)，大幅提升运行效率。

实现步骤 #

• 先将第三组flist转换为哈希集合，利用集合O(1)的查找特性快速判断目标值是否存在
• 遍历第一组所有元素作为首项a
• 遍历第二组所有元素作为第二项b
• 计算目标第三项target_c = 2*b - a，如果该值存在于第三组集合中，则(a, b, target_c)为符合要求的组合

示例代码 #

clist = [7, 11, 52, 102, 144, 314]
tlist = [10, 29, 79, 94, 121, 146]
flist = [13, 47, 184, 190, 544, 649]

# 预处理第三组为哈希集合
f_set = set(flist)
valid_combinations = []

for a in clist:
    for b in tlist:
        target_c = 2 * b - a
        if target_c in f_set:
            valid_combinations.append((a, b, target_c))

# 输出结果示例：[(7, 10, 13), (11, 29, 47)]
print(valid_combinations)

额外优化方向（超大量数据适用） #

如果三组数据量均超过百万级别，可以额外做如下优化：

• 提前对三组数据做去重处理，减少无效遍历
• 对第二组元素先做范围裁剪，过滤掉不可能满足2*b >= min(clist)+min(flist) 且 2*b <= max(clist)+max(flist)的无效值，缩小遍历范围
• 对第一组和第二组按数值分桶，进一步减少遍历次数

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