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 + nums > 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