查找未排序数组中是否有元素(x，y，z)，以便x+y=z
查找未排序数组中是否有元素(x，y，z)，以便x+y=z
提问于 2018-11-08 14:58:51
给定一个未排序的数组A1...n.Write，如果A中有三个元素Ai、Aj、Ak，则该算法返回true，以便Ai+ Aj = Ak，否则该算法必须返回false (请注意，这可能是Ai = Aj，并且它是合法的)。所需时间为O(n^2)。我提出了一个在O(n^2 * log(n))中工作的算法。我的算法对数组进行排序，然后对每一对两个元素x，y使用二进制搜索来确定是否有一个元素x+y。是否有一个更快的解，取O(n^2)？
回答 2
Stack Overflow用户
回答已采纳
发布于 2018-11-08 15:23:00
您可以先对数组进行排序- O(nlogn)
然后，它归结为在任何元素A[k]的元素A[0] .. A[k-1]中找到两个A[k]和。
排序数组的两个和可以用两个指针技术在O(n)中找到，如下所示：
boolean searchSum( int k, int[] A ) {
if ( k > A.length - 1 || k < 2 ) return false;
i = 0, j = k-1
while ( i < j ) {
if (A[i] + A[j] == A[k])
return true;
else if (A[i] + A[j] < A[k])
i++;
else
j--;
}
return false;
}对于每一个k，它是O(k-1)，总的来说，复杂性应该是O(n^2)。
您可以像这样调用searchSum：
boolean myMethod( int[] A ) {
sort(A);
for ( int i = A.length - 1; i >= 2; i-- ) {
if ( searchSum( i, A ) ) {
return true;
}
}
return false;
}Stack Overflow用户
发布于 2018-11-08 15:03:24
您可以创建具有O(1)查找功能的A元素的哈希表，并将其用于搜索x+y。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/53210351
复制相关文章
相似问题
腾讯云开发者
