Python高效实现：计算列表中两不同元素的有效组合数（解决10^5量级数据超时问题）

嘿，我完全懂你遇到的困境——你原来用itertools.combinations的写法逻辑上是对的，但当n达到10^5的时候，这种暴力枚举所有组合的思路肯定会超时，因为总组合数是n*(n-1)/2，当n=1e5时这个数接近5e9量级，根本不可能在500ms内完成。

我们可以换个数学思路来解决，用总组合数减去相同元素的组合数，这样就能把时间复杂度降到O(n)，轻松应对1e5级别的数据：

核心思路 #

1. 先计算从n个元素中选2个的总组合数：公式是 total = n * (n - 1) // 2（整数除法避免浮点误差）
2. 统计每个元素在数组中出现的次数，用collections.Counter就能高效完成
3. 对每个出现k次的元素，计算它能组成的相同元素组合数：k * (k - 1) // 2，把所有这些值累加得到same_pairs
4. 最终有效组合数 = 总组合数 - 相同元素组合数

例子验证 #

拿你给的输入举例：

• n=3，数组是[1,7,1]
• 总组合数：3*2//2 = 3
• 元素1出现2次，相同组合数：2*1//2=1；元素7出现1次，相同组合数为0
• 最终结果：3-1=2，和预期输出完全一致

高效代码实现 #

from collections import Counter
import sys

def count_different_pairs():
    # 用sys.stdin加快输入速度，处理1e5量级数据时很关键
    input_data = sys.stdin.read().split()
    n = int(input_data[0])
    arr = list(map(int, input_data[1:n+1]))
    
    # 统计每个元素的出现频率
    freq_counter = Counter(arr)
    
    # 计算所有可能的两两组合数
    total_pairs = n * (n - 1) // 2
    
    # 计算所有相同元素的两两组合数之和
    same_element_pairs = 0
    for count in freq_counter.values():
        same_element_pairs += count * (count - 1) // 2
    
    # 有效组合数 = 总组合数 - 相同元素组合数
    print(total_pairs - same_element_pairs)

if __name__ == "__main__":
    count_different_pairs()

为什么这个方法更快？ #

• 你原来的方法是**O(n²)**时间复杂度，枚举所有组合的操作量会随着n的增大爆炸式增长，1e5元素的场景下完全无法运行
• 新方法是**O(n)**时间复杂度：仅需遍历一次数组统计频率，再遍历一次不同元素计算相同组合数，整个过程在毫秒级就能完成1e5量级的数据处理

测试你的例子：
输入：

3
1 7 1

输出：

2

完全符合预期，而且不管n多大，这个方法都能轻松在时间限制内跑完~

备注：内容来源于stack exchange，提问作者Bá Đình Phạm