16. 3Sum Closest

two pointers O(n²)

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        n, d, res = len(nums), float('inf'), 0
        for i in range(n):
            if i > 0 and nums[i - 1] == nums[i]: continue
            l, r, t = i + 1, n - 1, target - nums[i]
            while l < r:
                s = nums[l] + nums[r]
                if abs(s - t) < d:
                    d, res = abs(s - t), s + nums[i]
                if s < t:
                    l += 1
                    while l < r and nums[l - 1] == nums[l]:
                        l += 1
                elif s > t:
                    r -= 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1
                else:
                    return res
        return res

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int i = 0;
        int diff = INT_MAX;
        int res = 0;
        while (i < n) {
            int l = i + 1, r = n - 1;
            int t = target - nums[i];
            while (l < r) {
                int sum = nums[l] + nums[r];
                if (abs(sum - t) < diff) {
                    diff = abs(sum - t);
                    res = nums[i] + sum;
                }
                if (sum == t) {
                    return target;
                } else if (sum < t) {
                    do { ++l; } while (l < r && nums[l] == nums[l - 1]);
                } else {
                    do { --r; } while (l < r && nums[r] == nums[r + 1]);
                }
            }
            do { ++i; } while (i < n && nums[i] == nums[i - 1]);
        }
        return res;
    }
};