16. 3Sum Closest #

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.

Example:

Given array nums = [-1, 2, 1, -4], and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Problem Summary #

Given an array, find the sum of 3 numbers in this array that is closest to target.

Solution Approach #

At first glance, this problem looks very similar to Problem 15 and Problem 18; they are all problems about finding the sum of 3 or 4 numbers. However, the approach for this problem is completely different from Problems 15 and 18.

The solution to this problem is to use the two-pointer approach. First sort the array, then let i scan from the beginning to the end. Here, we also need to pay attention to the issue of multiple duplicate numbers in the array. There are many specific ways to handle this, such as using a map to count and remove duplicates. Here the author uses a simple approach: during the loop, compare i with the previous number; if they are equal, continue moving i backward until it reaches the next position where the number differs from the previous one. The two pointers j and k then start moving inward from both ends. j is the next number after i, and k is the last number in the array. Since the array has been sorted, the number at k is the largest. j moves backward, k moves forward, gradually narrowing down to the value closest to target.

This problem can also be solved by brute force, using three nested loops to find the combination closest to target. See the code for details.

Code #

package leetcode

import (
	"math"
	"sort"
)

// Solution 1 O(n^2)
func threeSumClosest(nums []int, target int) int {
	n, res, diff := len(nums), 0, math.MaxInt32
	if n > 2 {
		sort.Ints(nums)
		for i := 0; i < n-2; i++ {
			if i > 0 && nums[i] == nums[i-1] {
				continue
			}
			for j, k := i+1, n-1; j < k; {
				sum := nums[i] + nums[j] + nums[k]
				if abs(sum-target) < diff {
					res, diff = sum, abs(sum-target)
				}
				if sum == target {
					return res
				} else if sum > target {
					k--
				} else {
					j++
				}
			}
		}
	}
	return res
}

// Solution 2 brute force solution O(n^3)
func threeSumClosest1(nums []int, target int) int {
	res, difference := 0, math.MaxInt16
	for i := 0; i < len(nums); i++ {
		for j := i + 1; j < len(nums); j++ {
			for k := j + 1; k < len(nums); k++ {
				if abs(nums[i]+nums[j]+nums[k]-target) < difference {
					difference = abs(nums[i] + nums[j] + nums[k] - target)
					res = nums[i] + nums[j] + nums[k]
				}
			}
		}
	}
	return res
}

func abs(a int) int {
	if a > 0 {
		return a
	}
	return -a
}