如何用Python找出所有两两等距的点三元组？

给定一个有序的数值列表，我们需要找出所有满足两两等距的三元组（即三元组(a, b, c)满足 b - a = c - b，等价于 2*b = a + c）。

示例 #

输入点列表：

points = [1, 2, 4, 6, 7, 8]

预期结果：

res = [(1, 4, 7), (2, 4, 6), (4, 6, 8), (6, 7, 8)]

符合条件的三元组解释：

• (1,4,7): 中间点4到1的距离等于到7的距离（差值为3）
• (2,4,6): 中间点4到2的距离等于到6的距离（差值为2）
• (4,6,8): 中间点6到4的距离等于到8的距离（差值为2）
• (6,7,8): 中间点7到6的距离等于到8的距离（差值为1）

基础实现方案 #

最直接的方式是遍历所有可能的三元组组合，判断是否满足等距条件：

points = [1, 2, 4, 6, 7, 8]
result = []
n = len(points)

# 遍历所有i<j<k的组合
for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            a, b, c = points[i], points[j], points[k]
            if b - a == c - b:
                result.append((a, b, c))

print(result)

这段代码会输出预期的结果，但时间复杂度为O(n³)，适合小数据量的场景。

优化实现方案 #

利用列表有序的特性，我们可以通过数学推导减少不必要的遍历：对于每个中间点points[j]和左侧点points[i]，计算出需要的右侧目标值target = 2*points[j] - points[i]，然后检查目标值是否存在于列表中且位置在j之后。

借助集合和字典可以快速完成存在性和位置判断，将时间复杂度降到O(n²)：

points = [1, 2, 4, 6, 7, 8]
point_set = set(points)
# 建立值到索引的映射，用于快速判断位置
point_index_map = {val: idx for idx, val in enumerate(points)}
result = []
n = len(points)

for i in range(n):
    for j in range(i + 1, n):
        target = 2 * points[j] - points[i]
        # 检查目标值存在且索引在j之后
        if target in point_set and point_index_map[target] > j:
            result.append((points[i], points[j], target))

print(result)

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