LeetCode Problem

Problem Description

Given an integer array nums of length n, find three integers in nums such that the sum is closest to a given number, target.

Examples

Input: [-1,2,1,-4], target = 1
Output: 2

Input: [0,0,0], target = 1
Output: 0

Input: [1,1,1,1], target = 3
Output: 3

Constraints

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10^4 <= target <= 10^4

Follow-up

Approach to Solve

Sort the array and use a two-pointer technique to find the triplet with the sum closest to the target.

Code Implementation

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        closest_sum = float('inf')
        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1
            while left < right:
                current_sum = nums[i] + nums[left] + nums[right]
                if abs(current_sum - target) < abs(closest_sum - target):
                    closest_sum = current_sum
                if current_sum < target:
                    left += 1
                else:
                    right -= 1
        return closest_sum

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closestSum = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length - 2; i++) {
            int left = i + 1, right = nums.length - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                if (Math.abs(currentSum - target) < Math.abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return closestSum;
    }
}

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int closestSum = INT_MAX;
        for (int i = 0; i < nums.size() - 2; i++) {
            int left = i + 1, right = nums.size() - 1;
            while (left < right) {
                int currentSum = nums[i] + nums[left] + nums[right];
                if (abs(currentSum - target) < abs(closestSum - target)) {
                    closestSum = currentSum;
                }
                if (currentSum < target) {
                    left++;
                } else {
                    right--;
                }
            }
        }
        return closestSum;
    }
};

Explanation

The 3Sum Closest problem is solved using a combination of sorting and two-pointer technique. Here's a detailed explanation of the approach:

Sort the input array: This is crucial for the two-pointer technique to work efficiently.
Initialize a variable 'closestSum' to store the sum closest to the target. Set it to a large value initially.
Iterate through the array: For each element nums[i], we'll find two other elements that, when summed with nums[i], are closest to the target.
- We only need to iterate up to the third-to-last element, as we need at least two more elements after i.
Two-pointer technique: For each i, initialize two pointers:
- left: points to the element right after i
- right: points to the last element of the array
While left < right:
- Calculate the currentSum = nums[i] + nums[left] + nums[right]
- If |currentSum - target| < |closestSum - target|, update closestSum to currentSum
- If currentSum < target, increment left (we need a larger sum)
- If currentSum >= target, decrement right (we need a smaller sum)
After the loop ends, return closestSum
Time Complexity: O(n^2)
- Sorting takes O(n log n)
- The nested loops (one explicit, one implicit in the while loop) take O(n^2)
- Overall, O(n log n + n^2) = O(n^2)
Space Complexity: O(1) or O(n)
- O(1) if we don't count the space for sorting (in-place sort)
- O(n) if we count the space for sorting (depends on the sorting algorithm used)

This approach efficiently finds the closest sum by leveraging the sorted nature of the array and using two pointers to adjust the sum towards the target. It handles all cases, including when the exact target sum is found or when the closest sum is less than or greater than the target.

Complexity

Time Complexity: O(n^2)
Space Complexity: O(1)