# Best 3Sum Closest Solutions

• This problem is similar to other 3 sum problem in leetcode, and here we would describe several solutions to it.

Approach #1 Brute Force [Time Limit Exceeded]

Intuition
The simplest way to solve the problem is iterate all possibilities and check compare them, and you can get the answer.

Algorithm
Suppose we have i, j, k, which a = nums[i], b = nums[j], c = nums[k]. And i,j,k satisfy 0 <= i < j < k < n; If we use 3 for loop, we could iterate all conditions, and get the answer.

c++ code

``````class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
if (nums.size() < 3) return 0;
int n = nums.size();
int res = nums[n-1] + nums[n-2] + nums[n-3];
int t;
for (int i = 0; i < n; i++) {
for (int j = i+1; j < n; j++) {
for (int k = j+1; k < n; k++) {
t = nums[i] + nums[j] + nums[k];
if (abs(res-target) > abs(t-target)) {
res = t;
}
}
}
}
return res;
}
};
``````

Complexity Analysis
The complexity is O(n^3). Cause we use 3 for loop here, and each complexity is O(n). The this approach will exceed the time limit.

Approach #2 Two Pointers Method [Accepted]

Algorithm
Here we use 3 pointer to solve this problem.

1. Suppose we have a sorted array, if the array is no already sorted, we can use sort function to make it sorted.
2. Iterate through the nums, use i, which nums[i] is the first element. And we also have l and r, which the answer is equal to nums[i] + nums[l] + nums[r]. And the answer is the closest 3 sum to target.
3. The i is the id of the first element of the 3 sum, which 0 <= i < n; (Here n is the size of the nums). We iterate the nums use i, and let l = i+1, r = n-1;
4. If the nums[i] + nums[l] + nums[r] < target, it means we should let 3 sum become larger, and it can be closer to the target, so here we let l = l + 1. (don't forget that the nums is ordered now!!!)
5. if the nums[i] + nums[l] + nums[r] > target, it means we should let 3 sum become smaller.
6. Every time we compare the 3 sum to the result we get before, and finally, we could get the final result.

c++ code

``````class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
if (nums.size() < 3) return 0;
int n = nums.size();
int res = nums[n-1] + nums[n-2] + nums[n-3];
int l, r, t;
for (int i = 0; i < n; i++) {
l = i+1, r = n-1;
while (l < r) {
t = nums[i] + nums[l] + nums[r];
if (abs(res-target) > abs(t-target)) {
res = t;
}
if (t == target) return t;
if (t < target) l+=1;
else r-=1;
}
}
return res;
}
};
``````

Complexity Analysis
The outer for loop use O(n) to iterate all element in nums, and inner while loop is O(n), we use 2 pointers here, so the final complexity is O(n^2).

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.