arrays - 使用二进制搜索的三元组总和

Question

我正在考虑寻找三元组和的各种方法，我遇到了这个 finding a triplet having a given sum .所以我想尝试一下。

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--;

如果 third > 0，但低于 low 怎么办？

我读了另一个问题，它提出了一个 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 page上看到有一个击败 O(N^2 logN) 的二次解。