使用二进制搜索的三元组和 [英] triplet sum using binary search

问题描述

我正在考虑寻找三元组和的各种方法，并且遇到了这个找到具有给定总和的三元组。因此，我想尝试一下。

I was thinking of various approaches for finding the triplet sum and I came across this finding a triplet having a given sum. So I thought of giving it a try.

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

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

But I am not getting correct output. I don't know where my logic is wrong because its pretty much simple binary search. Below is what I have implemented. Please let me know my mistake

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，但是当输入为 {3,4,8,1,2,7,5}时返回false。 code>和sum = 20它返回true

I tried it with input {1,2,3,4,5,6} and sum=6 but it returns false and when input was {3,4,8,1,2,7,5} and sum=20 it returned true

推荐答案

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

I partially understood your idea, not completely. It seems like you are trying to solve the problem in O(n log(n)) time complexity and I am not confident that it is possible. I am not sure how you decide to do this:

           else
            low++; 

我怀疑在某些情况下您应该这样做

I doubt that in some cases maybe you should do

high--

有。我也不确定这段代码：

there. Also I am not sure about this piece of code:

if(third<0)
   high--;

如果三分之一> 0，但小于低怎么办？

What if third > 0, but it's less than low?

我读了另一个问题，它提出了O（n ^ 2 logn）解决方案，因此我在这里提供了这样一个解决方案（使用Java）。

I read the other question and it proposes a O(n^2 logn) solution, so I provided here such a solution (in Java).

这个想法是：在所有成对的元素中使用2个嵌套的for循环（i，j）进行迭代，并查找将补充其余三元组的第三个元素数组的值（使用二进制搜索-while循环完成查找。

The idea is: iterate with 2 nested for loops (i, j) through all pairs of elements and look up for the third element which would complement the triplet in the rest of the array (that lookup is done using binary search - the while loop.

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）。

I did some research and couldn't find a O(N logN) solution for this problem. Turns out this problem is popular as 3SUM. You can see on the Wiki page there is a Quadratic solution which beats the O(N^2 logN).

这篇关于使用二进制搜索的三元组和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！