Let an array and some number x be given. It is necessary to determine whether there are three numbers in it, the sum of which is equal to x. If there were two numbers, it would be possible to sort and bin search for each number a to check for x - a. And then how?

  • Are the elements positive? 4 cycle runs I think enough - Senior Pomidor
  • And in the same way ... sort out - and rushed. The loop is in the loop, and inside is your bin search. - Akina
  • Related question: Finding three elements in an array where sum is

1 answer 1

Update: the implementation of the algorithm below does not work. For example: find_triplet_sum([0, 1, 2, 4, 5], 8) does not find a triple index: 1, 2, 4.

To find the indices i,j,k in the array a , such that a[i] + a[j] + a[k] == x , there is an O(n * log n) algorithm (from the @olykos answer ):

  1. Sort array
  2. Select the lo , hi indices corresponding to the largest and smallest values ​​in the array (the first and last elements in the sorted array)

  3. Then, as long as you can select the third element between the lo, hi indices:

    • using binary search, we try to find i index, such that:

       a[lo] + a[i] + a[hi] == x

    • if found, then the algorithm is complete

    • if the amount is less, then increase lo (increase the smallest available element)
    • if the sum is more, then we decrease hi (we reduce the largest available element)
  4. If not found, the algorithm failed.

Implementation on Python:

 from bisect import bisect_left def find_triplet_sum(a, x): a.sort() lo, hi = 0, len(a) - 1 while lo + 1 < hi: i = bisect_left(a, x - a[lo] - a[hi], lo + 1, hi) # binary search assert lo < i triplet_sum = a[lo] + a[i] + a[hi] if i == hi or triplet_sum < x: # sum is too small lo += 1 elif triplet_sum > x: # sum is too big hi -= 1 else: # found assert lo < i < hi and triplet_sum == x return lo, i, hi raise ValueError("Can't find i,j,k such that: a[i] + a[j] + a[k] == x.")

where bisect_left() implements binary search . Example:

 >>> find_triplet_sum([0, 1, 2, 3, 4], 3) (0, 1, 2)
  • Not quite clear: if the amount is less . If the binary search fails, then some amounts may be less, and some more. - VladD
  • @VladD: on the next line in the answer: if the amount is more (more, less, equal - no other options) - jfs
  • Anyway, it is not clear. Binary search did not find anything - what amount are we talking about? - VladD
  • Example. Target sum 15, array [0,1,9,10]. 0 + 1 + 10 is too small, 0 + 9 + 10 is too much. Which of these two sums are we talking about? - VladD
  • one
    @VladD original answer uses the words "left and right halves." Comparison with the amount should have been the intention to reflect. But I'm not sure anymore. I will leave an answer so that people do not run into the same rake. - jfs