Finding a triple that has a given amount

Question

I am now struggling with these issues. The question is: -

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

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

Any help would be greatly appreciated.

thank

Answer 1

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

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

Answer 2

See if this helps.

Answer 3

.

This can be done in O (n ^ 2). You do not need to sort this.

This is an extension of the problem that requires summing two numbers in x, and the trick is to use a 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 the quick sorting method for triplets, which will be O (1).