h4c*_*k3d 49 language-agnostic algorithm
我们需要在数组中找到一对数,其总和等于给定值.
A = {6,4,5,7,9,1,2}
Sum = 10然后对是 - {6,4},{9,1}
我有两个解决方案.
sum-hash[i]哈希表中是否存在.但是,问题在于虽然第二种解决方案是O(n)时间,但也使用O(n)空间.
所以,我想知道我们是否可以在O(n)时间和O(1)空间中完成它.这不是功课!
Evg*_*uev 19
使用就地基数排序和OP的第一个解决方案与2个迭代器相互接近.
如果数组中的数字不是某种多精度数字并且例如是32位整数,则可以使用几乎没有额外空间(每次传递1位)在2*32次传递中对它们进行排序.或者2*8遍和16个整数计数器(每遍4位).
2迭代器解决方案的详细信息:
第一个迭代器最初指向排序数组的第一个元素并向前推进.第二个迭代器最初指向数组的最后一个元素并向后前进.
如果迭代器引用的元素总和小于所需的值,则前进第一个迭代器.如果它大于所需的值,则前进第二个迭代器.如果它等于所需的值,则成功.
只需要一次传递,因此时间复杂度为O(n).空间复杂度为O(1).如果使用基数排序,整个算法的复杂性是相同的.
如果您对相关问题感兴趣(总和超过2个数字),请参阅"具有固定子集大小的Sum子集"和"在数组中查找其总和最接近给定数字的三个元素".
小智 6
这是来自微软亚洲研究院的经典访谈问题.
如何在未排序的数组中查找等于给定总和的2个数字.
[1]蛮力解决方案
此算法非常简单.时间复杂度为O(N ^ 2)
[2]使用二进制搜索
使用bianry搜索找到每个arr [i]的Sum-arr [i],时间复杂度可以减少到O(N*logN)
[3]
在[2]算法上使用哈希基础并使用哈希,时间复杂度可以减少到O(N),但是这个解决方案将添加哈希的O(N)空间.
[4]最优算法:
Pseduo代码:
for(i=0;j=n-1;i<j)
if(arr[i]+arr[j]==sum) return (i,j);
else if(arr[i]+arr[j]<sum) i++;
else j--;
return(-1,-1);
要么
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.
而且,这个问题完全解决了吗？否.如果数字是N.这个问题将变得非常复杂.
然后问题:
如何找到具有给定数字的所有组合案例？
这是一个经典的NP-Complete问题,称为subset-sum.
要了解NP/NPC/NP-Hard,您最好阅读一些专业书籍.
参考文献:
[1] http://www.quora.com/Mathematics/How-can-I-find-all-the-combination-cases-with-a-given-number
[2] http://en.wikipedia .ORG /维基/ Subset_sum_problem
明显的解决方案是否不起作用（迭代每个连续的对）或者这两个数字是否按任何顺序排列？
在这种情况下，您可以对数字列表进行排序，并使用随机采样对排序后的列表进行分区，直到获得一个足够小的子列表以进行迭代。