[LeetCode 016] 3 Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Example
For example, given array S = {-1 2 1 -4}, and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Difficulty
Medium

Similar Problems
[LeetCode 15] Two Sum M [LeetCode 259] 3Sum Smaller M

Challenge
Time: O(n^2)
Space: O(1)

Analysis

This is a variation of 3 Sum problem

Condition

Similary to 3 Sum

Idea

Distance between integers. minDist = int1 - int2 Use similary algorithm with 3 Sum. Sort the array and then use two indexers to process.

We can calculate an initial value (e.g. int delta = nums[0] + nums[1] + nums[2] - target) instead of use the INT_MAX.
Store last calculated distance and continuesly compare/update it with the current distance.

每轮循环，固定当前第 i 个元素，然后移动 start 和 end 两个游标，找到目标 sum 。

Demo
when minDist is 0, it is the minimum we can get, we should return it immediately. when minDist > curDist, we update minDist = curDist

then, continue to check below conditions:

• when minDist < 0, we move up begin pointer -> begin++
• when minDist > 0, we move down end pointer -> end--

Solutions

1. C++ Solution 13 ms

class Solution {
public:
    int threeSumClosest(vector<int> nums, int target) {
        const int n = nums.size();
        sort(nums.begin(), nums.end());

        int delta = nums[0] + nums[1] + nums[2] - target;
        for (int i = 0; i < n - 2; i++) {
            int start = i + 1, end = n - 1;
            while (start < end) {
                int d = nums[i] + nums[start] + nums[end] - target;
                if (d == 0) return target;
                if (abs(d) < abs(delta)) delta = d;
                else if (d < 0) start++;
                else end--;
            }
        }

        return delta + target;
    }
};

1. C++ Solution 23 ms

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int n = nums.size();
        if (n < 3) return INT_MAX;
        sort(nums.begin(), nums.end());

        int mindiff = INT_MAX;
        for(int i = 0; i < n - 2; ++i) {
            int a = nums[i], start = i + 1, end = n - 1;
            while(start < end) {
                int b = nums[start], c = nums[end];
                int diff = (a + b + c) - target;

                if(diff == 0) return target + diff;
                if(abs(mindiff) > abs(diff)) mindiff = diff;
                if(diff < 0) ++start;
                else if(diff > 0) --end;
            }
        }
        return target + mindiff;
    }
};

1. Golang Solution 12 ms

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    minDelta := nums[0] + nums[1] + nums[2] - target
    for i := 0; i < len(nums) - 2; i++ {
        begin, end := i + 1, len(nums) - 1
        for begin < end {
            delta := nums[i] + nums[begin] + nums[end] - target
            if delta == 0 {
                return delta + target
            } else if math.Abs(float64(delta)) < math.Abs(float64(minDelta)) {
                minDelta = delta
            }
            if delta < 0 {
                begin++
            } else if delta > 0{
                end--
            }
        }
    }

    return minDelta + target
}