我们如何在数组中找到唯一的对？

Question

查找数组中所有唯一的元素对，其总和为 S.Forex。如果数组 = {2,4,6,4,6} 且 S = 8，那么答案是 {(2,6), (4,4)}。我知道打印数组中所有对的解决方案，但如何做我们打印独特的对？

Answer 1

这是我的版本。希望有帮助。在 python 中工作。

array = [0, 1, 2, 3, 4, 5, 6]
S = 6
pairs = []

shift = 0
for i in array:
    shift += 1
    for j in array[shift:]:
        if S == (i+j):
            if (i,j) not in pairs and (j,i) not in pairs:
                pairs.append((i,j))
print pairs

Answer 2

不确定您是否正在寻找一些不同的语法或方法，但我确信应该有几个 lambda 表达式解决方案可以以更奇特的方式找到您的问题的答案。

a = [1, 2, 3, 4, 5]
pairs = []
append_flag = True
S = 6

for index1, element1 in enumerate(a):
  for index2, element2 in enumerate(a):
    if index1 != index2 and (element1 + element2) == S:
      append_flag = True
      for p in pairs:
        if ( (p[1] == element1 and p[0] == element2) or (p[0] == element1 and p[1] == element2) ):
         append_flag = False      
      if append_flag:
        pairs.append( [element1,element2] )

print pairs

这适用于Python

Answer 3

我在

java

中的实现在开头包含排序并找到一个元素而不进行比较。

public final class Pair {

    private final int first;
    private final int second;

    public Pair(int first, int second) {
        this.first = first;
        this.second = second;
    }

}

public static List<Pair> findUniquePairs(int[] arr, int s) {
    List<Pair> pairs = new ArrayList<>();
    Arrays.sort(arr);

    for (int i = 0; i < arr.length - 1; i++) {
        if (arr[i] >= s)
            break;

        Set<Integer> tmp = new HashSet<>();

        for (int j = i + 1; j < arr.length; j++) {
            if (arr[j] >= s)
                break;
            if (arr[i] + arr[j] != s || tmp.contains(arr[j]))
                continue;
            tmp.add(arr[j]);
            pairs.add(new Pair(arr[i], arr[j]));
        }
    }

    return pairs;
}

Answer 4

对于任何数字

x

，都存在一个对应的数字（无论是否在输入数组中）

c

，其总和等于目标值

S

。这个值是

c = S - x

，（从

x + c = S

重新排列）。

初始化一个哈希集，它将存储我们在输入数组中遇到的所有值。现在迭代输入数组。对于每个数字

x

，检查您是否已经遇到匹配的数字

c

。如果有，那么您就找到了一对。最后将数字添加到看到的数字哈希集中。

这是 Python 中的实现：

seen = set()
pairs = set()

for number in array:
    complement = S - number
    if complement in seen:
        pairs.add((complement, number))
    seen.add(number)

print(pairs)

为什么这个解决方案有效？

哈希集在恒定时间内计算集合中是否存在元素，这意味着无论哈希集包含多少个元素，它每次都会以大致相同的速度计算元素成员资格并添加元素。这意味着该解决方案的运行时间仅增加等于

n

，其中

n

是输入数组的长度。

如果我们使用嵌套 for 循环来检查每一对，则运行时间将增加等于

n(n-1)/2

，因为这就是存在的唯一对的数量。从时间复杂度分析来看，运行时间分别为

O(n)

vs

O(n²)

。