3 Sum Closest

Problem

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.

Analysis

思路，类似于 3 Sum 问题，不同之处在于寻找与target的绝对值最小的数；同样可以利用two pointers，对于 a + b + c 中的 b, c 来作为两个指针，a 为 num[i], 那么b初始值则为 num[i + 1], c初始值为num[len - 1]; 通过比较每次 a + b + c 的sum与target的大小，来确定移动b，或者移动c。

Solution

public class Solution {
    /**
    * @param numbers: Give an array numbers of n integer
    * @param target : An integer
    * @return : return the sum of the three integers, the sum closest target.
    */
    public int threeSumClosest(int[] numbers,int target) {
        if (numbers == null || numbers.length < 3) {
            return Integer.MAX_VALUE;
        }

        Arrays.sort(numbers);

        int diff = Integer.MAX_VALUE / 2;
        int length = numbers.length;
        int sign = 1;

        for (int i = 0; i < length - 2; i++) {
            int pl = i + 1;
            int pr = length - 1;

            while (pl < pr) {
                int sum = numbers[i] + numbers[pl] + numbers[pr];
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    if (target - sum < diff) {
                        diff = target - sum;
                        sign = -1;
                    }
                    pl++;
                } else {
                    if (sum - target < diff) {
                        diff = sum - target;
                        sign = 1;
                    }
                    pr--;
                }
            }
        }
        return target + sign * diff;
    }

}

Two Pointer - Use Math.abs() - (10ms, 78.40%)

// Use Math.abs(), two pointers
class Solution {
    public int threeSumClosest(int[] numbers, int target) {
        if (numbers == null || numbers.length < 3) {
            return Integer.MAX_VALUE;
        }

        Arrays.sort(numbers);

        int length = numbers.length;
        int closest = Integer.MAX_VALUE / 2;

        for (int i = 0; i < length - 2; i++) {
            int pl = i + 1;
            int pr = length - 1;

            while (pl < pr) {
                int sum = numbers[i] + numbers[pl] + numbers[pr];
                if (sum == target) {
                    return sum;
                } else if (sum < target) {
                    pl++;
                } else {
                    pr--;
                }
                closest = Math.abs(sum - target) < Math.abs(closest - target) ?
                    sum : closest;
            }
        }
        return closest;
    }
}

Two Pointer - (11ms 65.24%) - Time O(n^2), Space O(1)

基于3Sum，别忘了，先sort这个数组。

外层i = 0, ... , nums.length - 2;内层j = i + 1, k = nums.length - 1，这样再根据nums[j] + nums[k] vs target - nums[i]的比较，来移动j或者k指针。

记录与target最小的gap，minGap；用Math.abs()进行比较，这样minGap可以保留符号，最后closest = target + minGap

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = target;
        int minGap = Integer.MAX_VALUE / 2;
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1, k = nums.length - 1;
            int t = target - nums[i];
            while (j < k) {
                if (Math.abs(nums[j] + nums[k] - t) < Math.abs(minGap)) {
                    minGap = nums[j] + nums[k] - t;
                }
                if (nums[j] + nums[k] > t) {
                    k--;
                } else if (nums[j] + nums[k] < t) {
                    j++;
                } else {
                    // found 3sum equals target
                    return target;
                }
            }
        }
        closest = target + minGap;
        return closest;
    }
}