16. 3Sum Closest

• Time: $O(n^2)$
• Space: $O(|\texttt{ans}|)$
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 class Solution { public: int threeSumClosest(vector& nums, int target) { int ans = nums[0] + nums[1] + nums[2]; sort(nums.begin(), nums.end()); for (int i = 0; i + 2 < nums.size(); ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; // Choose nums[i] as the first num in the triplet, // and search the remaining nums in [i + 1, n - 1] int l = i + 1; int r = nums.size() - 1; while (l < r) { const int sum = nums[i] + nums[l] + nums[r]; if (sum == target) return sum; if (abs(sum - target) < abs(ans - target)) ans = sum; if (sum < target) ++l; else --r; } } return ans; } }; 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 class Solution { public int threeSumClosest(int[] nums, int target) { int ans = nums[0] + nums[1] + nums[2]; Arrays.sort(nums); for (int i = 0; i + 2 < nums.length; ++i) { if (i > 0 && nums[i] == nums[i - 1]) continue; // Choose nums[i] as the first num in the triplet, // and search the remaining nums in [i + 1, n - 1] int l = i + 1; int r = nums.length - 1; while (l < r) { final int sum = nums[i] + nums[l] + nums[r]; if (sum == target) return sum; if (Math.abs(sum - target) < Math.abs(ans - target)) ans = sum; if (sum < target) ++l; else --r; } } return ans; } } 
  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 class Solution: def threeSumClosest(self, nums: List[int], target: int) -> int: ans = nums[0] + nums[1] + nums[2] nums.sort() for i in range(len(nums) - 2): if i > 0 and nums[i] == nums[i - 1]: continue l = i + 1 r = len(nums) - 1 while l < r: summ = nums[i] + nums[l] + nums[r] if summ == target: return summ if abs(summ - target) < abs(ans - target): ans = summ if summ < target: l += 1 else: r -= 1 return ans