3Sum Closest - Two pointers in sorted array

Array     Medium     Sorting     Two Pointers    

Problem Statement:

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.

 

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
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).

 

Constraints:

• 3 <= nums.length <= 500
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

Solution:

Any 3 sum problem is best solved by sorting the array and then doing the two pointer method (O(n^2)).

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) 
    {
        int n = nums.size(), closest=nums[0]+nums[1]+nums[2];
        sort(nums.begin(), nums.end());
        for (int i=0; i<n-2; i++)
        {
            int lo=i+1, hi=n-1;
            while (lo<hi)
            {
                int curr = nums[i]+nums[lo]+nums[hi];
                if (curr==target) return target;
                if (abs(target-curr)<abs(target-closest)) closest = curr;
                if (curr<target) lo ++;
                else hi--;
            }
        }
        return closest;
    }
};