.png)
Given an integer array nums of length n and an integer, find the three integers in nums whose sum is closest to the given integer.
Return the addition of 3 integer numbers.
Let's consider that each input has only one solution.
Example 1:
Input: nums = [-1,2,1,-4], target = 1 Output: 2 Explanation: The closest sum to the goal is 0. (-1 + 2 + 1 = 2).
Example 2:
Input: nums = [0,0,0], target = 1 Output: 0 Explanation: The closest sum to the goal is 0. (0 + 0 + 0 = 0).
Constraints:
3 <= nums.length <= 1000-1000 <= nums[i] <= 1000-104 <= target <= 104
Native brute force solution
3 nested loops can be used to consider every triplet in the given array and determine if the desired sum is found.
An efficient approach using hashing to solve the 3-sum problem algorithm.
In this approach, we assume that the triplet can be broken down as a pair plus one extra element. Thus we can use the 2 sum algorithm's logic to solve it.
Conceptually this is how it works.
- We store each element from the array in the map along with its index.
- Then we consider all the pairs in the array and check if the map has the remaining sum or not.
- If the index of the remaining sum is not overlapping with the pair indexes then triplets exist and thus return true, false otherwise.
𝐂++ 𝐒𝐨𝐥𝐮𝐭𝐢𝐨𝐧
class Solution{
public:
int threeSumClosest(vector<int>& nums,int target){
sort(nums.begin(),nums.end());
int ans=0;
int diff=INT_MAX;
for(int i=0; i<nums.size(); i++){
int s=i+1;
int e=nums.size()-1;
while(s<e){
if(nums[i]+nums[s]+nums[e]==target) return target;
else if(abs(nums[i]+nums[s]+nums[e]-target)<diff){
diff=abs(nums[i]+nums[s]+nums[e]-target);
ans=nums[i]+nums[s]+nums[e];
}
if(nums[i]+nums[s]+nums[e]>target)
e--;
else
s++;
}
}
return ans;
}
};
Success
Details Runtime: 593 ms, faster than 26.07% of C++ online submissions for 3Sum Closest.
Memory Usage: 16.5 MB, less than 45.35% of C++ online submissions for 3Sum Closest.