Problem Specification

Given an integer array nums containing n elements and a specific target value, the objective is to identify three distinct integers within the array such that their sum is nearest to the target. The function should return this specific sum. It is guaranteed that a unique optimal solution exists for every input.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum closest to the target is 2 (-1 + 2 + 1 = 2).

Example 2:

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

Constraints:

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

Algorithmic Strategy

To achieve an efficient solution, the input array should first be sorted. This ordering allows for the application of the two-pointer technique, reducing the search space significantly. The process involves iterating through each element to serve as the first number of the triplet, while two pointers scan the remaining sub-array to find the other two numbers.

1. Sort: Arrange nums in ascending order.
2. Iterate: Loop through the array, fixing one element at a time.
3. Two Pointers: For each fixed element, initialize a left pointer at the next index and a right pointer at the end of the array.
4. Evaluate: Calculate the sum of the triplet. Track the sum with the smallest absolute difference from the target.
5. Adjust: If the current sum is less than the target, increment the left pointer to increase the sum. If greater, decrement the right pointer. If equal, return immediately.

Implementation

import java.util.Arrays;

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int limit = nums.length;
        int optimalResult = nums[0] + nums[1] + nums[2];

        for (int index = 0; index < limit - 2; index++) {
            int low = index + 1;
            int high = limit - 1;

            while (low < high) {
                int tripletSum = nums[index] + nums[low] + nums[high];
                
                if (Math.abs(target - tripletSum) < Math.abs(target - optimalResult)) {
                    optimalResult = tripletSum;
                }

                if (tripletSum < target) {
                    low++;
                } else if (tripletSum > target) {
                    high--;
                } else {
                    return tripletSum;
                }
            }
        }
        return optimalResult;
    }
}

Complexity Breakdown

Time Efficiency

The dominant factor is the nested loop structure. Sorting requires O(n log n). The outer loop runs n times, and the inner while loop processes the remaining elements in linear time relative to the sub-array size. Consequently, the total time complexity is O(n^2).

Space Efficiency

Aside from the input storage, only a few primitive variables are used for tracking pointers and sums. Assuming the sorting algorithm uses O(log n) stack space or is ignored for auxiliary space analysis, the extra space complexity is considered O(1).

Core Concepts

• Sorting: Essential for enabling pointer movement logic based on sum comparison.
• Pointer Manipulation: Dynamical adjusting indices to converge on the target value.
• Absolute Difference: Using Math.abs to measure proximity regardless of whether the sum is above or below the target.
• Early Exit: Returning immediately when an exact match is found saves unnecessary iterations.