给定一个长度为 n 的整数数组，需快速统计所有下标不同、但元素值不相等的二元组 (i, j)（i给定一个长度为 n 的整数数组，需快速统计所有下标不同、但元素值不相等的二元组 (i, j)（i
在处理大规模数组（如 n = 10⁵）时，暴力枚举所有组合（共约 5×10⁹ 对）会严重超时。原方案使用
itertools.combinations(arr, 2)并逐对比较值是否相等，时间复杂度为 O(n²)，无法通过 500ms 时限。更优解法基于补集思想：
先计算所有可能的无序下标对总数，再减去「值相等」的配对数，即：不相等配对数 = 总配对数 − 相等配对数
- 总配对数：从 n 个元素中任选 2 个，即组合数 C(n, 2) =
n * (n - 1) // 2；- 相等配对数：对每个重复出现的数值 x（出现频次为 v），其内部可构成 C(v, 2) =
v * (v - 1) // 2个相等配对；将所有数值的该值求和即可。该算法仅需一次遍历统计频次（O(n)），再遍历频次字典（最多 O(n) 个不同值），整体时间复杂度为 O(n)，空间复杂度为 O(u)（u 为不同元素个数），完全满足大数据量要求。
以下是完整实现：
from collections import Counter def count_different_pairs(n, arr): # 统计每个数字的出现频次 freq = Counter(arr) # 总无序对数：C(n, 2) total_pairs = n * (n - 1) // 2 # 所有值相等的配对数之和 same_pairs = sum(v * (v - 1) // 2 for v in freq.values()) return total_pairs - same_pairs # 示例验证 n = 3 arr = [1, 7, 1] print(count_different_pairs(n, arr)) # 输出：2 # 更多测试用例 print(count_different_pairs(4, [2, 2, 2, 2])) # 0（全相同） print(count_different_pairs(4, [1, 2, 3, 4])) # 6（全不同 → C(4,2)=6）✅ 注意事项：
立即学习“Python免费学习笔记（深入）”；
- 输入数组元素可为任意整数（包括负数、零），
Counter完全支持；- 使用整数除法
//避免浮点误差；- 不依赖下标顺序，仅关注值的分布，因此无需排序或额外索引结构；
- 若需返回具体配对（而非仅数量），则必须回退至 O(n²) 方法——本题仅计数，故此优化成立。
该方法是典型“计数优化”范式：避开显式构造，转而用数学归纳与频次聚合实现线性突破。
