检查数组中的两个数字是否相加等于I

Question

我看到一个面试问题如下：

给出一个未排序的整数数组A和一个整数I，找出是否有任何两个A的成员相加等于I。

有什么线索吗？

时间复杂度应该要小。

- mindtree

Answer 1

将元素插入哈希表中。

在插入 x 时，检查是否已经存在 I-x。预期时间为 O(n)。

否则，按升序对数组进行排序（从索引0到n-1）。有两个指针，一个在最大值处，一个在最小值处（分别称为 M 和 m）。

If a[M] + a[m] > I then M-- 
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.

- Aryabhatta

---

HashMap在最好的情况下性能非常好。但是在最坏的情况下（每个数字产生相同的哈希值），你就不会喜欢它了。 - yankee

@yankee：你能告诉我一个库的名字，它有一个现成且实用的哈希表实现，每次都会产生相同的哈希值吗？ - GManNickG

@EOL:这是针对整个数组的O(n) 预期 时间，而不仅仅是一个元素。 - Aryabhatta

第二种解决方案的简洁性值得点赞。谢谢！ - Ritesh

这两个解决方案比“已接受”的解决方案更好，更通用。 - kharles

Answer 2

例如，循环并将可能的数字添加到集合或哈希表中，如果找到，则直接返回。

>>> A = [11,3,2,9,12,15]
>>> I = 14
>>> S = set()
>>> for x in A:
...     if x in S:
...         print I-x, x
...     S.add(I-x)
...
11 3
2 12
>>>

- YOU

---

这是O(n)级别的。S中的x是O(1)，S.add(I-x)也是O(1)，最坏情况是O(n) - https://wiki.python.org/moin/TimeComplexity - Rohit

Answer 3

如果您知道整数的取值范围，可以使用类似于计数排序的解决方案，扫描数组并计算一个数组。例如，如果您有整数：

input = [0,1,5,2,6,4,2]

你可以像这样创建一个数组：

count = int[7]

在Java、C#等语言中，适合用于计算0到6之间整数的算法。

foreach integer in input
    count[i] = count[i] + 1

这将给你数组[1,1,2,0,1,1,1]。现在，您可以扫描这个数组的一半并检查是否有整数相加等于i，例如：

for j = 0 to count.length - 1
    if count[j] != 0 and count[i - j] != 0 then // Check for array out-of-bounds here
         WUHUU! the integers j and i - j adds up

总体而言，该算法的时间复杂度为O(n + k)，其中n是对长度为n的输入进行扫描，k是对长度为k（介于0和k-1之间的整数）的计数数组进行扫描。这意味着如果n > k，则您将获得保证的O(n)解决方案。

- Lasse Espeholt

---

这很好，但对于像 input = [0, 250, 500, 750, 1000] 这样的边缘情况，您需要一个巨大的数组来存储计数。我宁愿使用哈希表。 - José Tomás Tocino

Answer 4

1. 对数组进行排序。
2. 对于A中的每个元素X，执行二分搜索查找I-X。如果I-X在A中，则我们有一个解决方案。

这是O(nlogn)的算法。

如果A包含给定范围内的整数（足够小），我们可以使用一个技巧使其变为O(n)：

1. 我们有一个数组V。对于A中的每个元素X，我们将V[X]加1。
2. 当我们增加V[X]时，我们还会检查V[I-X]是否大于0。如果是，则我们有一个解决方案。

- Gabi Purcaru

---

使用哪种算法对数组进行排序？ - yankee

дҪ д№ҹеҸҜд»ҘеңЁжҺ’еәҸж•°з»„ж—¶дёўејғд»»дҪ•еӨ§дәҺI-1зҡ„йЎ№пјҢд»ҘдҪҝжҗңзҙўжӣҙеҝ«пјҢе°Ҫз®ЎжңҖеқҸжғ…еҶөдёӢзҡ„жҖ§иғҪжҳҜзӣёеҗҢзҡ„гҖӮ - Dan Grossman

@yankee 堆排序，归并排序，快速排序（不是最坏情况下的 O(n*log n)）。 - Lasse Espeholt

@Dan: 你不能这样做，因为列表中可能会有负整数。负整数和正整数相加的结果可能会超过I。 - yankee

排序后，更好的方法是只在两端各有1个指针，然后将它们向内移动。看看Aryabhatta的解决方案。 - kharles

Answer 5

public static boolean findSum2(int[] a, int sum) {
        if (a.length == 0) {
            return false;
        }
        Arrays.sort(a);


        int i = 0;
        int j = a.length - 1;
        while (i < j) {
            int tmp = a[i] + a[j];
            if (tmp == sum) {
                System.out.println(a[i] + "+" + a[j] + "=" + sum);
                return true;
            } else if (tmp > sum) {
                j--;
            } else {
                i++;
            }
        }
        return false;
}

- naani

Answer 6

O(n) time and O(1) space

如果数组已经排序，则时间复杂度为O(n)。

假设我们的数组是 array = {0, 1, 3, 5, 8, 10, 14} 如果我们的x1 + x2 = k = 13，则输出应为= 5, 8

步骤如下：

1.取两个指针，一个在数组开始处，另一个在数组末尾处

2.将ptr1和ptr2处的元素相加： array[ptr1] + array[ptr2] 3.如果和大于k，则将ptr2减一，否则将ptr1加一

4.重复步骤2和步骤3，直到ptr1 != ptr2

更详细的解释可以参考这里。看起来像是亚马逊的面试题。 http://inder-gnu.blogspot.com/2007/10/find-two-nos-in-array-whose-sum-x.html

- EFreak

---

糟糕..我读错了问题！以为它已经排序了。但无论如何，由于它与上下文相关，我还是保留答案。 - EFreak

Answer 7

使用PERL实现检测已排序数组中是否包含两个整数，它们的和为Number

my @a = (11,3,2,9,12,15);
my @b = sort {$a <=> $b} @a;

my %hash;
my $sum = 14;
my $index = 0;
foreach my $ele (@b) {
    my $sum_minus_ele = $sum - $ele;
    print "Trace: $ele :: $index :: $sum_minus_ele\n";
    if(exists($hash{$sum_minus_ele}) && $hash{$sum_minus_ele} != $index ) {
        print "\tElement: ".$ele." :: Sum-ele: ".$sum_minus_ele."\n";
    }
    $hash{$ele} = $index;
    $index++;
}

- Alexsea

Answer 8

for each ele in the array
  if (sum - ele) is hashed and hashed value is not equal to index of ele
    print ele, sum-ele
  end-if
  Hash ele as key and index as value
end-for

- codaddict

Answer 9

Python的实现

def func(list,k):
temp={} ## temporary dictionary
for i in range(len(list)):
    if(list[i] in temp): ## if temp already has the key just increment its value
        temp[list[i]] +=1
    else:  ## else initialize the key in temp with count as 0
        temp[list[i]]=0 

    if(k-list[i] in temp and ((k/2 != list[i]) or temp[list[i]]>=1)): ## if the corresponding other value to make the sum k is in the dictionary and its either not k/2 or the count for that number is more than 1
        return True

return False

输入： list是一个数字列表（问题中的A）...
k是总和（问题中的I）....

如果存在一对列表中的数字之和等于k，则该函数输出True，否则输出False...

我使用了一个字典，其键是数组（列表）中的元素，值是该元素在列表中出现的次数。 平均运行时间复杂度为O(n)。

此实现还处理了两个重要的边缘情况：

• 列表中有重复的数字
• 不重复添加相同的数字。

- Prasanna Natarajan

Answer 10

这个问题可以使用并查集算法来解决，该算法可以在常数时间内检查一个元素是否属于一个集合。

因此，算法如下：

foundsum0 = false;
foreach (el: array) {
    if find (-x): foundsum0 = true;
    else union (x);
}

FIND 和 UNION 是常数时间的，O(1)。

- alinsoar