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

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 但它 returns 为假，当输入为 {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)。

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

triplet sum using binary search

arrays

algorithm

binary-search