O(n^2) 52ms Python solution, easy to understand


  • 0
    Y

    The intuition is, fixing a number n1, we find the other two (n2, n3) such that they sum up close to target. For example, if target - n1 is 5, we want n2 + n3 close to 5. We start the search with both n2 and n3 close to the expected average of them, i.e. 5/2.

    Say now we have n2 = 2 and n3 = 4, and n2 + n3 is bigger than the expected sum (5), so we go for a smaller n2 (decrement p2); if n2 + n3 is smaller than the expected sum, we increment p3.

    The tricky part is when there are duplicated values that equal to the expected average. If the array contains ...2, 2, 2... when we are looking for a sum of 4 (n_avg = 2), we want to point both p2 and p3 to cells that have 2. Otherwise we miss the opportunity of having n2 = n3 once we increment p3 or decrement p2.

    def threeSumClosest(nums, target):
    	nums.sort()
    	p_avg = len(nums) - 1
    	best_error, best_error_abs = None, None
    	for p1, n1 in enumerate(nums):
    		# calculate n_avg, the expected average of n2 and n3
    		complement = target - n1
    		n_avg = complement / 2
    		# decrement p_avg to point to n_avg
    		while p_avg >= 0 and nums[p_avg] > n_avg:
    			p_avg -= 1
    		if p_avg > 0 and nums[p_avg-1] == n_avg: p_avg -= 1
    		if p_avg == -1:
    		    if best_error is not None and n1 + nums[0] + nums[1] > target - best_error:
    		        break
    		    else:
    		        p_avg = 0
    		elif p_avg == len(nums) - 1: p_avg = len(nums) - 2
    		# search for n2 and n3, keeping n2 <= n3
    		p2, p3 = p_avg, p_avg + 1
    		while True:
    			if p2 == p1: p2 -= 1
    			elif p3 == p1: p3 += 1
    			if p2 < 0 or p3 >= len(nums): break
    			n2, n3 = nums[p2], nums[p3]
    			error = complement - n2 - n3
    			if error == 0: return target
    			error_abs = abs(error)
    			if best_error_abs is None or error_abs < best_error_abs:
    				best_error, best_error_abs = error, error_abs
    			if error > 0: p3 += 1
    			else: p2 -= 1
    	return target - best_error

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.