NUHMAN.com

Introduction

LeetCode 16: 3Sum Closest is a follow-up to the popular 3Sum problem. Here, instead of finding triplets that sum up to zero, your goal is to find a triplet whose sum is closest to a given target.

In this article, we’ll explore an efficient solution using sorting and the two-pointer technique, and implement it cleanly in Go (Golang).

Problem Statement

Given an integer array nums of length n 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.

Examples

go

Input: nums = [-1, 2, 1, -4], target = 1
Output: 2
Explanation: The closest sum is -1 + 2 + 1 = 2
go

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

Approach: Sorting + Two Pointers

1. Sort the array.
2. Fix one element i, then use two pointers (left and right) to find the closest sum.
3. Track the closest sum seen so far by comparing the absolute difference from the target.

Why it works:

Sorting allows you to move the pointers smartly:

• Move left → right to increase the sum.
• Move right → left to decrease the sum.

Go Implementation

go

package main

import (
    "fmt"
    "math"
    "sort"
)

func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    closest := nums[0] + nums[1] + nums[2]

    for i := 0; i < len(nums)-2; i++ {
        left, right := i+1, len(nums)-1

        for left < right {
            sum := nums[i] + nums[left] + nums[right]

            if math.Abs(float64(sum-target)) < math.Abs(float64(closest-target)) {
                closest = sum
            }

            if sum < target {
                left++
            } else if sum > target {
                right--
            } else {
                return sum // exact match
            }
        }
    }

    return closest
}

func main() {
    testCases := []struct {
        nums   []int
        target int
    }{
        {[]int{-1, 2, 1, -4}, 1},
        {[]int{0, 0, 0}, 1},
        {[]int{1, 1, 1, 1}, 3},
        {[]int{-3, -2, -5, 3, -4}, -1},
    }

    for _, tc := range testCases {
        result := threeSumClosest(tc.nums, tc.target)
        fmt.Printf("Input: %v, Target: %d -> Closest Sum: %d\n", tc.nums, tc.target, result)
    }
}

Step-by-Step Example: [-1, 2, 1, -4], Target = 1

Sorted: [-4, -1, 1, 2]

• i = 0 → nums[i] = -4
• left = 1 (nums[left] = -1), right = 3 (nums[right] = 2)
• sum = -4 + -1 + 2 = -3 → update closest
• move left to 2 → sum = -4 + 1 + 2 = -1 → update closest
• move left to 3 → loop ends
• i = 1 → nums[i] = -1
• left = 2, right = 3
• sum = -1 + 1 + 2 = 2 → update closest
• 2 is closer to target 1 than -1

Result: 2

Time and Space Complexity

• Time Complexity: O(n²)
• Outer loop: O(n)
• Inner loop (two pointers): O(n)
• Space Complexity: O(1), ignoring sorting overhead.

Key Takeaways

• Sorting + two pointers = go-to strategy for many 2/3/4-sum variants.
• Always track the current closest using abs(sum - target).
• Efficient and easy to implement in Go.