3 Sum closest

16.3Sum Closest

Array

Two Pointers

Sorting

Problem Statement:

Given an integer array nums and a target value, find the sum of three integers in nums that is closest to the target. Return the sum of the three integers.

Example:

Input:

nums = [-1,2,1,-4], target = 1

→

Output:

2

Algorithm:

1. Sort array for two-pointer approach
2. Fix first element and use two pointers
3. Track minimum difference from target
4. Update closest sum when smaller diff found

Complexity:

Time: O(n²) | Space: O(1)

Java Solution:

public int threeSumClosest(int[] nums, int target) {
    if (nums == null || nums.length < 3) {
        return target;
    }
    
    Arrays.sort(nums);  // Sort for two-pointer approach
    
    int closest = 0;
    int min = Integer.MAX_VALUE;
    
    for (int i = 0; i < nums.length - 2; i++) {
        int j = i + 1;
        int k = nums.length - 1;
        
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
    
            int diff = Math.abs(target - sum);
            if (diff < min) {  // Update if closer to target found
                closest = sum;
                min = diff;
            }
            if (sum == target) {
                return sum;
            } else if (sum < target) {
                j++;
            } else {
                k--;
            }
        }
    }
    
    return closest;
}

Python Solution:

def threeSumClosest(self, nums: List[int], target: int) -> int:
    if not nums or len(nums) < 3:
        return target
        
    nums.sort()
    closest = nums[0] + nums[1] + nums[2]
    min_diff = float('inf')
    
    for i in range(len(nums) - 2):
        j, k = i + 1, len(nums) - 1
        
        while j < k:
            curr_sum = nums[i] + nums[j] + nums[k]
            curr_diff = abs(target - curr_sum)
            
            if curr_diff < min_diff:
                closest = curr_sum
                min_diff = curr_diff
                
            if curr_sum == target:
                return curr_sum
            elif curr_sum < target:
                j += 1
            else:
                k -= 1
    
    return closest

C++ Solution:

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        if (nums.size() < 3) {
            return target;
        }
        
        sort(nums.begin(), nums.end());
        int closest = nums[0] + nums[1] + nums[2];
        int min_diff = INT_MAX;
        
        for (int i = 0; i < nums.size() - 2; i++) {
            int j = i + 1;
            int k = nums.size() - 1;
            
            while (j < k) {
                int curr_sum = nums[i] + nums[j] + nums[k];
                int curr_diff = abs(target - curr_sum);
                
                if (curr_diff < min_diff) {
                    closest = curr_sum;
                    min_diff = curr_diff;
                }
                
                if (curr_sum == target) {
                    return curr_sum;
                } else if (curr_sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
        }
        
        return closest;
    }
};