Leetcode 16. 3Sum Closest

[medium]

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 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

  • 3 <= nums.length <= 10^3
  • -10^3 <= nums[i] <= 10^3
  • -10^4 <= target <= 10^4

[Java]

  1. TC(O²)
  2. track current min different from 3-SUM and target
  3. use Math.abs(sum — target) < Math.abs(result — target)
  4. use Arrays.sort first, so the array sort from small to large; use two pointer (start, end) to find the minium result

CS new grad, 6 years experience related to supply chain management. Located in Bay area