0016. Three Sum Closest

0016. Three Sum Closest#

Problem#

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#

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is 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
-104 <= target <= 104

Analysis#

This is similar to 0015. The closest value should lead the minimum of \(|a+b+c - target|\).

Solution 1: Naive The naive method can use three loops to find the minimum value, and will use \(O(n^3)\) time.

Solution 2: Sort + Two Pointer This solution is similar to 0015.

  • To build a pattern for search, we can first sort the array in a non-decending order. -> \(O(nlogn)\)

  • In the first loop, we can enumerate the array for the first number \(a=nums[i]\). -> \(O(n)\)

  • In the second loop, we can use the two-pointer algorithm for the rest of the array from \(i+1\) to \(n\) to enumerate \(b\) and \(c\). -> \(O(n)\)

    • use index \(j\) as the left pointer, and \(k\) as the right pointer. Assign \(b = nums[j]\) and \(c = nums[k]\). \(j\) starts from \(i+1\), and \(k\) starts from \(n\).

    • if \(a+b+c \ge target\), which means the value of \(|a+b+c-target|\) is still big and may be further reduced by moving the right pointer \(k\) one step left.

    • if \(a+b+c \lt target\), which means the value of \(|a+b+c-target|\) is still big and may be further reduced by moving the left pointer \(j\) one step right.

    • The loop should stop at

      • \(a+b+c-target=0\) or

      • \(j >= k\)

How to get \(k\) closest sum??

Solution#

# Solution 2: 
def solution(nums, target):
    nums.sort()
    best = 10000
     
    for i, a in enumerate(nums):
        j, k = i + 1, len(nums) - 1
        while j < k:
            s = a + nums[j] + nums[k]
            best = s if abs(s - target) < abs(best - target) else best
            if s > target: 
                k -= 1
            elif s < target:
                j += 1
            else:
                return target
        
    return best        

    # test
nums = [-1, 2, 1, -4]
target = 1
print(solution(nums, target))

nums = [0, 0, 0]
target = 1
print(solution(nums, target))

nums = [1, 1, 1, 1]
target = 100
print(solution(nums, target))

2
0
3

The above code can be improved:

  • skip duplicates as in 0015.

Contents