finding a triplet having a given sum

I have been struggl开发者_StackOverflowing with this questions for sometime now. The question goes like this:-

We have n^2 numbers. We need to find out if there exists a triplet a,b,c such that a+b+c = 0. For a more generic case, a+b+c = k. (k is given)

There exists a solution with O(n^2log(n)) complexity.

Any help would be greatly appreciated.

thanks

To get this in O(n²logn), you'd have to sort the numbers. Find all combinations of 2 numbers, and do a binary search to find the third.

The upper bound is much higher for the general version of the problem.

I wrote a rough solution.

It can definitely be done in O(n^2). You don't have to sort this.

It's an extension of the problem which requires summing two numbers to x and the trick is to use the hash table.

def triplets(l, total):
    """Sum of 3 numbers to get to total 
    Basically an extension of the 2 table 
    """
    l = set( l)
    d = { }

    for i in l:
        remain = total - i

        inside = {}
        for j in l:
            if i == j:
                continue
            inside[j] = remain -j

        d[i] = inside

    good = set()

    for first, dic in d.iteritems():
        for second, third in dic.iteritems():
            if third in l:
                good.add( tuple(sorted([first, second, third])) )

    for each in good: 
        print each

triplets( [2, 3, 4, 5, 6], 3+4+5)

NOTE: we can use a fast sorting method for triplets which will be O(1).