3Sum Closest - Go Solution

LeetCode

— 1 min read

Solving the LeetCode "3Sum Closest" Problem in Go

Difficulty: Medium | Tags: Array, Two Pointers, Sorting

Introduction

The "3Sum Closest" problem requires finding three numbers in an array whose sum is as close as possible to a given target. This problem is a variation of the classic "3Sum" problem and is commonly encountered in coding interviews.

Problem Analysis

Given an array of integers and a target value, we need to find a triplet (three numbers) whose sum is closest to the target. Unlike the standard "3Sum" problem, we don't need the exact sum but the closest possible one. The solution must efficiently handle arrays of varying sizes while minimizing computational overhead.

Solution Approach

The optimal approach involves sorting the array and using a two-pointer technique. By sorting the array, we can efficiently explore potential triplets. For each element, we use two pointers (left and right) to find the other two elements that, when combined, yield a sum closest to the target. We adjust the pointers based on whether the current sum is less than or greater than the target.

Go Implementation


package main
import (
"math"
"sort"
)
func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    n := len(nums)
    closestSum := nums[0] + nums[1] + nums[2]
    for i := 0; i < n-2; i++ {
        left, right := i+1, n-1
        for left < right {
            currentSum := nums[i] + nums[left] + nums[right]
            if math.Abs(float64(currentSum-target)) < math.Abs(float64(closestSum-target)) {
                closestSum = currentSum
            }
            if currentSum < target {
                left++
            } else if currentSum > target {
                right--
            } else {
                return currentSum
            }
        }
    }
    return closestSum
}

Complexity Analysis

Time Complexity: O(n²) - The algorithm involves sorting the array (O(n log n)) and then iterating through the array with nested loops (O(n²)), making the overall complexity O(n²).

Space Complexity: O(1) - The solution uses a constant amount of extra space, as it only requires a few variables to store intermediate results.

Testing and Examples

Example 1: nums = [-1,2,1,-4], target = 1 → Output: 2

Example 2: nums = [0,0,0], target = 1 → Output: 0

Edge Case: nums = [1,1,1,1], target = 0 → Output: 3 (sum of first three elements)

Best Practices and Tips

1. Always sort the array first to leverage the two-pointer technique efficiently.

2. Use absolute differences to compare how close the current sum is to the target.

3. Early termination can be added if the exact target sum is found.

4. Handle edge cases, such as very small or large target values, to ensure robustness.

Read more