检查，如果2个数字阵列加起来我 [英] checking if 2 numbers of array add up to I

问题描述

我看到一个面试问题如下： 给整数A和一个排序的数组和整型我，看看A的任何两个成员加起来我。

I saw a interview question as follows: Give an unsorted array of integers A and and an integer I, find out if any two members of A add up to I.

任何线索？

时间复杂度应小于

推荐答案

如果您有整数都在范围内，就可以使用，你扫描整个阵列计数排序解和计数阵列了。前有整数

If you have the range which the integers are within, you can use a counting sort-like solution where you scan over the array and count an array up. Ex you have the integers

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

和你创建一个这样的数组：

And you create an array like this:

count = int[7]

其中（使用Java，C＃等）适合于在0和6计数的整数。

which (in Java,C# etc.) are suited for counting integers between 0 and 6.

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

这会给你的数组 [1,1,2,0,1,1,1] 。现在，您可以通过扫描数组（它的一半），并检查是否有整数这加起来我喜欢

This will give you the array [1,1,2,0,1,1,1]. Now you can scan over this array (half of it) and check whether there are integers which adds up to i like

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'GT;氏/ code>，那么你必须保证 O（N）解决方案。

Overall this algorithm gives you O(n + k) where n is from the scan over the input of length n and k is the scan over the count array of length k (integers between 0 and k - 1). This means that if n > k then you have a guaranteed O(n) solution.

这篇关于检查，如果2个数字阵列加起来我的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！