使用二叉搜索的三元组和

Question

我在考虑各种方法来查找三元组和，我遇到了这个发现具有给定总和的三元组。所以我想试一试。

My algorithm:
1) Sort the numbers //O(nlogn)
2) Initialize low=0 and high=size-1
3) loop till low<high
a) if sum-arr[high]-arr[low]< 0 , then decrement high
b) if third number is not in range of (low,high) then break the loop
c) else search for third number using binary search

但我没有得到正确的输出。我不知道我的逻辑哪里有问题，因为它非常简单的二进制搜索。以下是我实施的内容。 请让我知道我的错误

static boolean isTriplet(int a[], int size, int sum)
{
Arrays.sort(a);  //sort the numbers
int low = 0;
int high = size-1;
while(low<high)
{
int third = sum - a[high] - a[low];
if(third<0)
high--;
else if(!(sum - a[high] - a[low]>a[low] && sum - a[high] - a[low]< a[high]))  //if the number is not within the range then no need to find the index
break;
else
{
int index = binarySearch(a,low+1,high-1,third);
if(index != -1)
{
System.out.println(a[low]+" "+a[index]+" "+a[high]);
return true;
}
else
low++;                  
}
}
return false;
}

我尝试使用输入{1,2,3,4,5,6}和 sum=6 进行，但它返回 false，当输入{3,4,8,1,2,7,5}并且 sum=20 时，它返回 true

Answer 1

我部分理解你的想法，不完全理解。似乎您正在尝试以 O(n log(n)) 时间复杂度解决问题，但我不确定这是可能的。我不确定您如何决定这样做：

else
low++; 

我怀疑在某些情况下也许你应该这样做

high--

那里。我也不确定这段代码：

if(third<0)
high--;

如果第三个> 0，但它低于低怎么办？

我读了另一个问题，它提出了一个 O(n^2 logn) 解决方案，所以我在这里提供了这样一个解决方案(在 Java 中)。

这个想法是：用 2 个嵌套的 for 循环 (i， j) 遍历所有元素对，并查找第三个元素，这将补充数组其余部分中的三元组(该查找是使用二进制搜索完成的 - while 循环。

public class TripletSum {
static boolean solve(int[] a, int k) {
Arrays.sort(a);
int n = a.length;
for(int i = 0; i < n; i++) {
for(int j = i + 1; j < n; j++) {
int low = j + 1, high = n - 1;
while(low <= high) {
int middle = (low + high) / 2;
int sum = a[middle] + a[i] + a[j];
if(sum == k) {
return true;
}
if(sum > k) {
high = middle - 1;
}
if(sum < k) {
low = middle + 1;
}
}
}
}
return false;
}
public static void main(String[] args) {
int[] a = {1,2,3,4,5,6};
System.out.println(solve(a, 20));
} 
}

编辑： 我做了一些研究，找不到这个问题的O(N logN)解决方案。事实证明，这个问题很流行为3SUM。你可以在 Wiki 页面上看到有一个二次解，它击败了 O(N^2 logN)。