16. 3Sum Closest - cocoder39/coco39_LC GitHub Wiki

16. 3Sum Closest

get the smallest num fixed and try to minimize the diff. Once diff is locked, 3-sum is derived from target and diff

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        diff = float('inf')
        for i, num in enumerate(nums):
            low, high = i+1, len(nums)-1
            while low < high:
                total = num + nums[low] + nums[high]
                new_diff = target - total
                if abs(new_diff) < abs(diff):
                    diff = new_diff
                    
                if total < target:
                    low += 1
                elif total > target:
                    high -= 1
                else:
                    return target
        
        return target - diff

==================================

extension of 2sum

public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int res = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int low = i + 1, high = nums.length - 1;
            while (low < high) {
                int sum = nums[i] + nums[low] + nums[high];
                if (Math.abs(target - sum) < Math.abs(target - res)) {
                    res = sum;
                }
                
                if (sum > target) {
                    high--;
                } else {
                    low++;
                }
            }
        }
        return res;
    }