如何高效计算两个边界定义的整数集合的交集？

完全理解你的痛点——当集合的范围很大时，生成完整的集合再求交集简直是灾难，不仅慢还会吃掉大量内存。其实根本不需要生成整个集合，咱们直接通过边界计算就能搞定，效率拉满！

核心思路 #

两个由(左边界, 右边界)定义的整数集合，它们的交集满足：

• 交集的左端点 = 两个集合左边界的最大值
• 交集的右端点 = 两个集合右边界的最小值
• 如果计算出的左端点 ≤ 右端点，说明存在交集，范围就是[左端点, 右端点]；否则交集为空

这种方法不需要生成任何完整集合，时间和空间复杂度都是O(1)，完全不受区间大小影响——哪怕你的区间是(1, 10^9)，计算也是瞬间完成的。

代码实现 #

1. 获取交集边界 #

如果你只需要知道交集的范围，直接返回边界即可：

def get_intersection_bounds(bounds1, bounds2):
    # 计算交集的左右边界
    intersect_left = max(bounds1[0], bounds2[0])
    intersect_right = min(bounds1[1], bounds2[1])
    # 判断是否存在交集
    return (intersect_left, intersect_right) if intersect_left <= intersect_right else None

2. 生成交集元素（内存友好） #

如果需要遍历交集的元素，用生成器代替集合可以避免占用大量内存：

def generate_intersection(bounds1, bounds2):
    intersect_left = max(bounds1[0], bounds2[0])
    intersect_right = min(bounds1[1], bounds2[1])
    if intersect_left <= intersect_right:
        # 用yield from生成元素，不会一次性加载到内存
        yield from range(intersect_left, intersect_right + 1)

示例使用 #

用你给出的测试案例验证：

set1_bounds = (1, 5)
set2_bounds = (2, 8)

# 获取交集边界
intersection_bounds = get_intersection_bounds(set1_bounds, set2_bounds)
print(f"交集边界: {intersection_bounds}")  # 输出: (2, 5)

# 遍历交集元素
for num in generate_intersection(set1_bounds, set2_bounds):
    print(num)  # 依次输出: 2, 3, 4, 5

对比原方法的优势 #

原方法通过生成集合求交集，时间和空间复杂度都是O(N)（N为集合元素个数）：

• 当区间很小的时候，差异不明显，但一旦区间扩大到百万、千万甚至更大，会直接耗尽内存（比如range(1, 10**9+1)生成的集合根本无法存储）
• 新方法完全没有这个问题，不管区间多大，计算成本都是固定的

如果确实需要一个set对象，也可以用set(generate_intersection(bounds1, bounds2))，但只推荐在区间较小时使用——大区间下还是用边界或生成器更高效。

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