我看到一个面试问题如下:
给出一个未排序的整数数组A和一个整数I,找出是否有任何两个A的成员相加等于I。
有什么线索吗?
时间复杂度应该要小。
我看到一个面试问题如下:
给出一个未排序的整数数组A和一个整数I,找出是否有任何两个A的成员相加等于I。
有什么线索吗?
时间复杂度应该要小。
x
时,检查是否已经存在 I-x
。预期时间为 O(n)
。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.
>>> 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
>>>
input = [0,1,5,2,6,4,2]
你可以像这样创建一个数组:
count = int[7]
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)
解决方案。
input = [0, 250, 500, 750, 1000]
这样的边缘情况,您需要一个巨大的数组来存储计数。我宁愿使用哈希表。 - José Tomás TocinoA
中的每个元素X
,执行二分搜索查找I-X
。如果I-X
在A
中,则我们有一个解决方案。这是O(nlogn)
的算法。
如果A
包含给定范围内的整数(足够小),我们可以使用一个技巧使其变为O(n)
:
V
。对于A
中的每个元素X
,我们将V[X]
加1。V[X]
时,我们还会检查V[I-X]
是否大于0。如果是,则我们有一个解决方案。I-1
зҡ„йЎ№пјҢд»ҘдҪҝжҗңзҙўжӣҙеҝ«пјҢе°Ҫз®ЎжңҖеқҸжғ…еҶөдёӢзҡ„жҖ§иғҪжҳҜзӣёеҗҢзҡ„гҖӮ - Dan Grossmanpublic 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;
}
O(n) time and O(1) space
array = {0, 1, 3, 5, 8, 10, 14}
如果我们的x1 + x2 = k = 13
,则输出应为= 5, 8array[ptr1] + array[ptr2]
3.如果和大于k,则将ptr2减一,否则将ptr1加一使用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++;
}
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
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)。
此实现还处理了两个重要的边缘情况:
这个问题可以使用并查集算法来解决,该算法可以在常数时间内检查一个元素是否属于一个集合。
因此,算法如下:
foundsum0 = false;
foreach (el: array) {
if find (-x): foundsum0 = true;
else union (x);
}
FIND 和 UNION 是常数时间的,O(1)。