如何在数组中查找唯一数对？含求和为S的唯一数对求解

嘿，我来帮你搞定这个问题！你已经能打印所有数对了，现在核心就是解决去重的问题——既要避免像(2,6)和(6,2)这种顺序不同但本质相同的数对，也要处理数组里重复元素带来的重复数对（比如原数组里的两个4，不能输出两次(4,4)）。我们分两种场景来拆解：

最简单的思路是先对数组排序，再遍历生成数对，同时跳过重复元素，最后用集合来自动去重（集合不会存储重复的元素）。

举个Python代码例子：

array = [2,4,6,4,6]
unique_pairs = set()

# 先排序，方便统一数对顺序和跳过重复元素
sorted_arr = sorted(array)

for i in range(len(sorted_arr)):
    # 跳过和前一个元素相同的i，避免重复生成以该元素开头的数对
    if i > 0 and sorted_arr[i] == sorted_arr[i-1]:
        continue
    for j in range(i, len(sorted_arr)):
        # 跳过和前一个元素相同的j（当j>i时），避免重复数对
        if j > i and sorted_arr[j] == sorted_arr[j-1]:
            continue
        # 把数对加入集合，自动去重
        unique_pairs.add( (sorted_arr[i], sorted_arr[j]) )

print(unique_pairs)
# 输出: {(2, 4), (2, 6), (4, 4), (4, 6), (6, 6)}

这里排序后，我们通过跳过重复元素，确保不会生成重复的数对，集合则帮我们兜底，保证最终结果的唯一性。

针对这个需求，有两种高效的方法：排序+双指针法和哈希表法，都能很好地解决去重问题。

方法1：排序+双指针法（适合空间要求较高的场景） #

先排序数组，然后用左右两个指针从两端向中间移动，找到和为S的数对后，跳过重复元素避免重复记录。

代码示例：

array = [2,4,6,4,6]
S = 8
unique_pairs = set()

sorted_arr = sorted(array)
left = 0
right = len(sorted_arr) - 1

while left <= right:
    current_sum = sorted_arr[left] + sorted_arr[right]
    if current_sum == S:
        # 存入排序后的数对，避免顺序不同的重复
        unique_pairs.add( (sorted_arr[left], sorted_arr[right]) )
        # 跳过左边所有重复的元素
        while left < right and sorted_arr[left] == sorted_arr[left+1]:
            left += 1
        # 跳过右边所有重复的元素
        while left < right and sorted_arr[right] == sorted_arr[right-1]:
            right -= 1
        # 移动指针继续寻找
        left += 1
        right -= 1
    elif current_sum < S:
        # 和太小，左指针右移找更大的数
        left += 1
    else:
        # 和太大，右指针左移找更小的数
        right -= 1

print(unique_pairs)
# 输出: {(2, 6), (4, 4)}

方法2：哈希表法（时间复杂度更低，O(n)） #

用一个集合记录已经遍历过的元素，对于每个元素，计算它的补数（S - 当前元素），如果补数已经在集合里，就把排序后的数对加入结果集合（避免顺序不同的重复）。

代码示例：

array = [2,4,6,4,6]
S = 8
seen = set()
unique_pairs = set()

for num in array:
    complement = S - num
    if complement in seen:
        # 排序数对，确保(2,6)和(6,2)被视为同一个
        pair = tuple(sorted( (num, complement) ))
        unique_pairs.add(pair)
    # 把当前元素加入已遍历集合
    seen.add(num)

print(unique_pairs)
# 输出: {(2, 6), (4, 4)}

这个方法速度更快，只需要遍历一次数组，但需要额外的空间存储已遍历元素。

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