LC 0016 [M] 3Sum Closest - ALawliet/algorithms GitHub Wiki

this is the only difference from regular 3Sum

if abs(target_diff) < abs(min_diff):
   min_diff = target_diff # save the closest and positive difference

class Solution:
    def threeSumClosest(self, arr: List[int], target_sum: int) -> int:
      n = len(arr)

      arr.sort()
      min_diff = math.inf # new

      for i in range(n - (3-1)):
        l = i + 1
        r = n - 1

        while l < r:
          s = arr[i] + arr[l] + arr[r]
          target_diff = target_sum - s

          if target_diff == 0: # we've found a triplet with an exact sum
            return s # return sum of all the numbers

          # the second part of the following 'if' is to handle the smallest sum when we have more than one solution
          if abs(target_diff) < abs(min_diff):
            min_diff = target_diff # save the closest and positive difference

          if target_diff > 0:
            l += 1 # we need a triplet with a bigger sum

          elif target_diff < 0:
            r -= 1 # we need a triplet with a smaller sum

      return target_sum - min_diff # new