16. 3Sum Closest - Medium

前往題目

想法

• 應該可以轉換2sum來做，但不知道有沒有更好的方法

思路

沒有更好的方法了，只能$O(N^2)$

1. 三個一組來看
2. 固定第一個，後兩個binary search
3. 每次都計算差，有更小就加到答案裡去(不要加成difference)

Code

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int length = nums.length;

        int minDiff = Integer.MAX_VALUE;
        int res = 0;
        // At least 3 elements until the end
        for (int i = 0; i < length - 2; ++i) {
            int l = i + 1, r = length - 1;

            // Binary search
            while (l < r) {
                int temp = nums[i] + nums[l] + nums[r];

                // Found closer value
                if (Math.abs(target - temp) < minDiff) {
                    res = temp;
                    minDiff = Math.abs(target - temp);
                }

                if (temp == target) return target;

                // Move right, closer to the target
                if (temp < target) {
                    ++l;
                } else { // Move left
                    --r;
                }
            }
        }
        return res;
    }
}