16. 3Sum Closest

https://leetcode.com/problems/3sum-closest/

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:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Constraints:

• 3 <= nums.length <= 10^3

• -10^3 <= nums[i] <= 10^3

• -10^4 <= target <= 10^4

Thoughts

数组中找三元组，它的和与target最近的。暴力法O(N^3)=>往O(N^2)优化。排序后nums[i]作为最大元素的候选，在i元素前找和最接近target-nums[i]的二元对，2sum。2sum用首尾双指针。

Code

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        diff, res = math.inf, 0 
        for i, num in enumerate(nums):
            l, r = 0, i - 1
            while l < r:
                s = sum((nums[l], nums[r], num))
                if s < target:
                    l += 1
                elif s > target:
                    r -= 1
                else:
                    return s
                if abs(s - target) < diff:
                    diff = abs(s - target)
                    res = s
        return res
        

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums == null && nums.length == 0) {
            return 0;
        }

        Arrays.sort(nums);
        int cloest = Integer.MAX_VALUE;
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            int l = i + 1, r = nums.length - 1;
            int res = target - nums[i]; 
            while (l < r) {
                if (Math.abs(nums[i] + nums[l] + nums[r] - target) < cloest) {
                    cloest = Math.abs(nums[i] + nums[l] + nums[r] - target);
                    sum = nums[i] + nums[l] + nums[r];
                }
                if (nums[l] + nums[r] < res) {
                    l++;
                } else if (nums[l] + nums[r] > res) {
                    r--;
                } else {
                    return target;
                }
            }
        }

        return sum;
    }
}

Analysis

Errors:

1. 不需要考虑目标(res)应是sum-target还是target-sum，因为算法都是尽量向target靠。

TC: $O(n^2)$