Coder's Cat

## LeetCode: 3Sum Closest

2019-10-23

Solution for LeetCode 3sum Closet, with Cpp/Java/Python

## LeetCode Problem

https://leetcode.com/problems/3sum-closest/

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:

## Explaination

Naive solution will enumerate the array with three loop:

The time complexity of course should be $O(N^3)$.

Actually this problem is almost same with previous LeetCode: 3Sum, except we need to find the closet sum of three elements.

Sort the array and use the method of fixing head or tail index, according to current sum, the complexity will be $O(N^2)$.

## Python

Preparing for an interview? Check out this!