3Sum Closest Problem and Solution

1. Introduction

A comprehensive guide to solving the "3Sum Closest" problem in multiple programming languages (C++, Java, and Python), including detailed explanations and outputs.

The "3Sum Closest" problem involves finding three integers in an array such that the sum is closest to a given target number. Unlike the regular "3Sum" problem, which seeks sums that exactly match a target, this variant focuses on minimizing the absolute difference between the sum of the triplets and the target.

2. Problem

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.

3. Solution in C++

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int closest = nums[0] + nums[1] + nums[2];
    for (int i = 0; i < nums.size() - 2; ++i) {
        int j = i + 1, k = nums.size() - 1;
        while (j < k) {
            int sum = nums[i] + nums[j] + nums[k];
            if (sum == target) return sum;
            if (abs(target - sum) < abs(target - closest)) {
                closest = sum;
            }
            if (sum < target) ++j;
            else --k;
        }
    }
    return closest;
}

// Example usage
int main() {
    vector<int> nums = {-1, 2, 1, -4};
    int target = 1;
    cout << "3Sum Closest: " << threeSumClosest(nums, target) << endl;
    return 0;
}

Output:

3Sum Closest: 2

Explanation:

1. threeSumClosest in C++ first sorts the array.

2. It uses a two-pointer technique, iterating through the array.

3. For each triplet, it checks if the sum is closer to the target than the current closest sum.

4. If an exact match is found, it returns immediately.

5. Otherwise, it updates the closest sum and continues.

4. Solution in Java

import java.util.*;

public class ThreeSumClosest {
    public static int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int closest = nums[0] + nums[1] + nums[2];
        for (int i = 0; i < nums.length - 2; i++) {
            int j = i + 1, k = nums.length - 1;
            while (j < k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == target) return sum;
                if (Math.abs(target - sum) < Math.abs(target - closest)) {
                    closest = sum;
                }
                if (sum < target) ++j;
                else --k;
            }
        }
        return closest;
    }

    // Example usage
    public static void main(String[] args) {
        int[] nums = {-1, 2, 1, -4};
        int target = 1;
        System.out.println("3Sum Closest: " + threeSumClosest(nums, target));
    }
}

Output:

3Sum Closest: 2

Explanation:

1. Java's threeSumClosest method also sorts the array.

2. It iterates through the array, using a two-pointer approach for each triplet.

3. Checks and updates the closest sum based on the absolute difference from the target.

4. Returns either an exact match or the closest sum found.

5. Solution in Python

def three_sum_closest(nums, target):
    nums.sort()
    closest = sum(nums[:3])
    for i in range(len(nums) - 2):
        j, k = i + 1, len(nums) - 1
        while j < k:
            sum_three = nums[i] + nums[j] + nums[k]
            if sum_three == target:
                return sum_three
            if abs(target - sum_three) < abs(target - closest):
                closest = sum_three
            if sum_three < target:
                j += 1
            else:
                k -= 1
    return closest

# Example usage
nums = [-1, 2, 1, -4]
target = 1
print("3Sum Closest:", three_sum_closest(nums, target))

Output:

3Sum Closest: 2

Explanation:

1. Python's three_sum_closest sorts the list first.

2. Uses a loop combined with two-pointer technique to find the closest sum.

3. Updates the closest sum based on its difference from the target.

4. Returns either the exact target sum or the closest sum found.