Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example:


Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Difficulty: interview

Starter code:

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        

Solutions:
class Solution(object):
     def threeSumClosest(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         size = len(nums)
         if size < 3:
             return 0
         nums.sort()
         i = 0 # fix the first index
         ans = nums[0] + nums[1] + nums[size - 1] # ans is used to record the solution
         while i < size - 2:
             tmp = target - nums[i]
             j = i + 1
             k = size - 1
             while j < k:
                 if nums[j] + nums[k] == tmp:
                     return target
                 if nums[j] + nums[k] > tmp:
                     if nums[j] + nums[j + 1] >= tmp:
                         if nums[j] + nums[j + 1] - tmp < abs(ans - target):
                             ans = nums[i] + nums[j] + nums[j + 1]
                         break
                     tmpans = nums[i] + nums[j] + nums[k]
                     if tmpans - target < abs(ans - target):
                         ans = tmpans
                     k -= 1
                 else:
                     if nums[k] + nums[k - 1] <= tmp:
                         if tmp - nums[k] -nums[k - 1] < abs(ans - target):
                             ans = nums[i] + nums[k - 1] + nums[k]
                         break
                     tmpans = nums[i] + nums[j] + nums[k]
                     if target - tmpans < abs(ans - target):
                         ans = tmpans
                     j += 1
             i += 1
             if ans == target:
                 return target
         return ans

class Solution:
     def threeSumClosest(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         Solution: Sort the list then use three pointers (i, j, k) to find the sum of 3 values that is closest to target.
         Store the current closest value and the distance from target.
         Current closest value can be compared using abs(target - value) and comparing to the stored distance from target.
         """
         arr, i, closest, dist = nums, 0, None, None
         arr.sort()
 
         if len(arr) == 3:
             return arr[0] + arr[1] + arr[2]
 
         while i < len(arr) - 2:
             if i > 0 and arr[i] > target:
                 return closest
             if i == 0 or arr[i] != arr[i - 1]:
                 j, k = i + 1, len(arr) - 1
                 while j < k:
                     val = arr[i] + arr[j] + arr[k]
                     if val == target:
                         return val
                     temp_dist = abs(target - val)
                     # print('VALS', arr[i], arr[j], arr[k], val, temp_dist)
                     if dist == None or temp_dist < dist:
                         closest = val
                         dist = temp_dist
                     if val < target:
                         j += 1
                     else:
                         k -= 1
 
             i += 1
         return closest

class Solution:
     def threeSumClosest(self, array, target):
         """ Returns sum of integers from array closest to target.
         Time complexity: O(n ^ 2). Space complexity: O(n),
         where n is len(array).
         """
         array.sort()
 
         n = len(array)
         best_sum = float("inf")  # closest sum of 3 integers so far
         for i in range(n - 2):  # choosing the 1st integer
             if i > 0 and array[i] == array[i - 1]:  # skip duplicates
                 continue
 
             diff = target - array[i]  # best sum for 2 other integers
             x, y = i + 1, n - 1
             best_diff = float("inf")
             while x < y:
                 curr_diff = array[x] + array[y]
                 if curr_diff == diff:  # exact sum we're looking for
                     return target
                 elif curr_diff < diff:  # increase current sum of 2 integers
                     x += 1
                 else:  # curr_diff > diff, decrease current sum of 2 integers
                     y -= 1
                 # update best difference so far
                 if abs(curr_diff - diff) < abs(best_diff - diff):
                     best_diff = curr_diff
 
             # update best sum if needed
             curr_sum = array[i] + best_diff
             if abs(curr_sum - target) < abs(best_sum - target):
                 best_sum = curr_sum
         return best_sum

class Solution:
     def threeSumClosest(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         if len(nums) < 3:
             return sum(nums)
         elif len(nums) == 3:
             return sum(nums)
         nums = sorted(nums)
         res = nums[0]+nums[1]+nums[2]
         for i in range(len(nums) - 2):
             if i!= 0 and nums[i] == nums[i-1]:
                 continue
             j = i+1
             k = len(nums) - 1
             while j < k:
                 s = nums[i] + nums[j] + nums[k]
                 if s == target:
                     return target
                 if s < target:
                     j += 1
                 else:
                     k -= 1                
                 if abs(s-target) < abs(res-target):
                     res = s
         return res

class Solution:
     def threeSumClosest(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         nums = sorted(nums)
         res, diff = None, None
         for first in range(len(nums) - 2):
             if first and nums[first] == nums[first - 1]:
                 continue
                 
             second, third = first + 1, len(nums) - 1
             if diff is None:
                 res = nums[first] + nums[second] + nums[third]
                 diff = abs(res - target)
             while second < third:
                 three_sum = nums[first] + nums[second] + nums[third]
                 if three_sum == target:
                     return target
                 elif three_sum < target:
                     partial = nums[first] + nums[third]
                     while second < third and nums[second] + partial  < target:
                         second += 1
                     tmp = nums[second - 1] + partial
                     if abs(tmp - target) < diff:
                         diff = abs(tmp - target)
                         res = tmp
                 else:
                     partial = nums[first] + nums[second]
                     while second < third and partial + nums[third] > target:
                         third -= 1
                     tmp = partial + nums[third + 1]
                     if abs(tmp - target) < diff:
                         diff = abs(tmp - target)
                         res = tmp
         return res
             


class Solution:
     def threeSumClosest(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         '''
         nums = sorted(nums)
         size = len(nums)
         res = list()
         for i in range(size-2):
             if i and nums[i] == nums[i-1]:
                 continue
             left, right = i+1, size-1
             while left < right:
                 sums = nums[i] + nums[left] + nums[right]
                 if sums == target:
                     return target
                 else:
                     res.append(sums)
                     if sums < target:
                         while left < right and nums[left] == nums[left+1]:
                             left += 1
                         left += 1
                     else:
                         while left < right and nums[right] == nums[right-1]:
                             right -= 1
                         right -= 1
         return self.helper(res, target)
     
     def helper(self, nums, target):
         if not nums:
             return
         goal = abs(nums[0] - target)
         res = nums[0]
         for num in nums[1:]:
             if abs(num-target) < goal:
                 goal = abs(num-target)
                 res = num
         return res
 
         '''        
         nums = sorted(nums)
         size = len(nums)
         res = None
         diff = None
         for i in range(size-2):
             if i and nums[i] == nums[i-1]:
                 continue
             left, right = i+1, size-1
             if not diff:
                 res = nums[i] + nums[left] + nums[right]
                 diff = abs(res-target)
             while left < right:
                 sums = nums[i] + nums[left] + nums[right]
                 if sums == target:
                     return target
                 elif sums < target:
                     partial = nums[i] + nums[right]
                     while left < right and nums[left] == nums[left+1]:
                         left += 1
                     while left < right and partial+nums[left] < target:
                         left += 1
                     tmp = partial + nums[left-1]
                     if abs(tmp-target) < diff:
                         res, diff = tmp, abs(tmp-target)
                 else:
                     partial = nums[i] + nums[left]
                     while left < right and nums[right] == nums[right-1]:
                         right -= 1
                     while left < right and partial+nums[right] > target:
                         right -= 1
                     tmp = partial + nums[right+1]
                     if abs(tmp-target) < diff:
                         res, diff = tmp, abs(tmp-target)
         return res


class Solution(object):
     def threeSumClosest(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         size = len(nums)
         if size < 3:
             return 0
         nums.sort()
         i = 0 # fix the first index
         ans = nums[0] + nums[1] + nums[size - 1] # ans is used to record the solution
         while i < size - 2:
             tmp = target - nums[i]
             j = i + 1
             k = size - 1
             while j < k:
                 if nums[j] + nums[k] == tmp:
                     return target
                 if nums[j] + nums[k] > tmp:
                     if nums[j] + nums[j + 1] >= tmp:
                         if nums[j] + nums[j + 1] - tmp < abs(ans - target):
                             ans = nums[i] + nums[j] + nums[j + 1]
                         break
                     tmpans = nums[i] + nums[j] + nums[k]
                     if tmpans - target < abs(ans - target):
                         ans = tmpans
                     k -= 1
                 else:
                     if nums[k] + nums[k - 1] <= tmp:
                         if tmp - nums[k] -nums[k - 1] < abs(ans - target):
                             ans = nums[i] + nums[k - 1] + nums[k]
                         break
                     tmpans = nums[i] + nums[j] + nums[k]
                     if target - tmpans < abs(ans - target):
                         ans = tmpans
                     j += 1
             i += 1
             if ans == target:
                 return target
         return ans

class Solution:
     def threeSumClosest(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         nums.sort()
         result = nums[0]+nums[1]+nums[2]
         for i in range(len(nums) - 2):
             if i > 0 and nums[i] == nums[i - 1]:
                 continue
             if nums[i] + nums[i + 1] + nums[i + 2] > target + abs(result - target):
                 return result
             st = i + 1
             ed = len(nums) - 1
             while st < ed:
                 dis = nums[i] + nums[st] + nums[ed] - target
                 if dis == 0:
                     return target
                 elif dis > 0:
                     while st < ed and nums[i] + nums[st] + nums[ed] - target > 0:
                         ed -= 1
                     if abs(nums[i] + nums[st] + nums[ed + 1] - target) < abs(result - target):
                         result = nums[i] + nums[st] + nums[ed + 1]
                 else:
                     while st < ed and nums[i] + nums[st] + nums[ed] - target < 0:
                         st += 1
                     if abs(nums[i] + nums[st - 1] + nums[ed] - target) < abs(result - target):
                         result = nums[i] + nums[st - 1] + nums[ed]
         return result

class Solution:
     def threeSumClosest(self, nums, target):
         res = 0
         nlen = len(nums)
         if nlen < 3:
             for num in nums:
                 res += num
             return res
 
         lastdiff = sys.maxsize
         previous = None
         nums = sorted(nums)
         for idx in range(nlen - 2):
             num = nums[idx]
             if num == previous:
                 continue
             i = idx + 1
             j = nlen - 1
             previous = num
             cur_sum = num
 
             while i < j:
                 diff = 0
                 cur_sum += (nums[i] + nums[j])
                 if cur_sum == target:
                     return cur_sum
                 if cur_sum < target:
                     diff = target - cur_sum
                     i += 1
                 else:
                     diff = cur_sum - target
                     j -= 1
                 if diff < lastdiff:
                     lastdiff = diff
                     res = cur_sum
                 cur_sum = num
 
         return res

class Solution:
     def threeSumClosest(self, nums, target):
         """
         :type nums: List[int]
         :type target: int
         :rtype: int
         """
         if len(nums) <= 3:
             return sum(nums)
         nums.sort()
         diff=float('inf')
         
         for idx, num in enumerate(nums[:-2]):
             if idx>= 1 and num == nums[idx-1]:
                 continue
             start, end = idx + 1, len(nums) - 1
             while start < end:
                 temp_sum = nums[start] + nums[end]
                 new_target = target - num
                 if temp_sum == new_target:
                     return target
                 elif temp_sum > new_target:
                     end -= 1
                 else:
                     start += 1
                 
                 if abs(new_target - temp_sum) < diff:
                     if new_target - temp_sum < 0:
                         sign = -1
                     else:
                         sign = 1
                     diff = abs(new_target - temp_sum)
 
 
         return target - sign*diff