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).

Source: leetcode | Difficulty: MEDIUM_HARD
Tags: Data structures

Sorting

Amortized analysis

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

Solutions:
class Solution(object):

	def threeSumClosest(self, nums, target):
		size = len(nums)
		if size < 3:
			return 0
		nums.sort()
		i = 0
		ans = nums[0] + nums[1] + nums[size - 1]
		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):
		(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)
					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):
		array.sort()
		n = len(array)
		best_sum = float('inf')
		for i in range(n - 2):
			if i > 0 and array[i] == array[i - 1]:
				continue
			diff = target - array[i]
			(x, y) = (i + 1, n - 1)
			best_diff = float('inf')
			while x < y:
				curr_diff = array[x] + array[y]
				if curr_diff == diff:
					return target
				elif curr_diff < diff:
					x += 1
				else:
					y -= 1
				if abs(curr_diff - diff) < abs(best_diff - diff):
					best_diff = curr_diff
			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):
		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):
		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):
		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:

	def threeSumClosest(self, nums, target):
		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):
		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