16. 3Sum Closest

三刷 06/2022

Version #1 Two Pointers

如果用binary search是O(N^2logN)比Two Pointers慢

Time O(N^2) + O(logN) ~ O(N^2)

Space O(logN) to O(N) used by the sorting

Runtime: 106 ms, faster than 17.99% of Java online submissions for 3Sum Closest.

Memory Usage: 54.3 MB, less than 5.76% of Java online submissions for 3Sum Closest.

class Solution {

    public int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);

        int closestSum = 0;

        int diff = Integer.MAX_VALUE;

        for (int i = 0; i < nums.length; i++) {

            if (i != 0 && nums[i] == nums[i - 1]) {

                continue;

            }

            int start = i + 1, end = nums.length - 1;

            while (start < end) {

                int sum = nums[i] + nums[start] + nums[end];

                if (Math.abs(target - sum) < diff) {

                    diff = Math.abs(target - sum);

                    closestSum = sum;

                }

                if (sum == target) {

                    return target;

                }

                if (sum < target) {

                    start++;

                } else {

                    end--;

                }

            }

        }

        return closestSum;

    }

}

Version #2
TreeMap
想了一下是N^2logN 不合适


Version #1 Two Pointers

二刷
22.96 %
class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length < 3) {
            throw new IllegalArgumentException();
        }
        int diff = Integer.MAX_VALUE;
        int result = 0;
        Arrays.sort(nums);
        for (int i = 0; i < nums.length; i++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < diff) {
                    diff = Math.abs(sum - target);
                    result = sum;
                }
                if (sum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return result;
    }
}

一刷
3Sum 是当3sum == 0的时候有一个check and skip的过程，跳过所有重复的数值
这里如果相等就直接返回了因为没有比相等更小的diff
我在思考是不是也可以跳
如果跳的话写成
46.55 %
if (sum == target) {
                    return sum;
                } else if (sum > target) {
                    while (left < right && nums[right] == nums[right - 1]) right--;
                    right--;
                } else {
                    while (left < right && nums[left] == nums[left + 1]) left++;
                    left++;
                }
注意在while loop以外一定还有一次操作，否则就死循环了
改完以后是有些画蛇添足了

84.75 %
public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null || nums.length <= 2) return -1;
     
        int left, right;
        int resultSum = nums[0] + nums[1] + nums[nums.length - 1];
        Arrays.sort(nums);
        // nums.length - 2   nums.length - 1
        //i, left,           right
     
        for (int i = 0; i < nums.length - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) continue;
            left = i + 1;
            right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (Math.abs(sum - target) < Math.abs(resultSum - target)) {
                    resultSum = sum;
                }
                if (sum == target) {
                    return sum;
                } else if (sum > target) {
                    right --;
                } else {
                    left++;
                }
            }
        }
        return resultSum;
    }
}