[LeetCode] 16. 3Sum Closest

Posted on | In

Problem

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
2
3
Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Explanation

  1. Similar to 15. 3Sum, first, sort the array. We need to fix one number, then use two pointers technique to find the sum of 3 elements, and compare the sum with the target to get the newDiff. Since we are looking for the closest sum, we need to define a diff variable as the minimum diff. In other words, if newDiff is less than diff, then update diff to newDiff. Note, we should use absolute value to find newDiff.

Solution

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
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int closest = nums[0] + nums[1] + nums[2];
        int diff = Math.abs(target - closest);
        Arrays.sort(nums);

        for (int i = 0; i < nums.length-2; i++) {
            int fix = nums[i];
            int left = i + 1, right = nums.length-1;
            while (left < right) {
                int sum = fix + nums[left] + nums[right];
                int newDiff = Math.abs(target - sum);
                if (newDiff < diff) {
                    diff = newDiff;
                    closest = sum;
                }
                if (sum < target) {
                    left += 1;
                } else {
                    right -= 1;
                }
            }
        }
        return closest;
    }
}