Leetcode journey - Question 16 - 3Sum Closest

Problem:

Q16. 3Sum Closest

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 <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

Solution:

Approach:

After looking at the question, I thought of using a 2 pointer approach , I use j as the value next toi and k as the last element. I used a for loop to iterate through the vector nums. I used a while loop to iterate upto j<k. I used a if-else statement to check if the sum is less than the target. If it is, then I increment the value of j. If it is not, then I decrement the value of k. I used a if statement to check if the difference between the sum and the target is less than the minDiff. If it is, then I update the value of minDiff and ans.

Now, we can write the code:

Code:

#include <bits/stdc++.h>
using namespace std;

class Solution
{
public:
    int threeSumClosest(vector<int> &nums, int target)
    {
        int n = nums.size();
        int ans = 0;
        int minDiff = INT_MAX;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < n - 2; i++)
        {
            int j = i + 1;
            int k = n - 1;
            while (j < k)
            {
                int sum = nums[i] + nums[j] + nums[k];
                int diff = abs(sum - target);
                if (diff < minDiff)
                {
                    minDiff = diff;
                    ans = sum;
                }
                if (sum < target)
                {
                    j++;
                }
                else
                {
                    k--;
                }
            }
        }
        return ans;
    }
};

int main()
{
    Solution s;
    // [1,1,1,1]
    // -100
    vector<int> nums = {1, 1, 1, 1};
    cout << s.threeSumClosest(nums, -100) << endl;
    return 0;
}

Complexity Analysis:

Time Complexity: O(n^2)
Space Complexity: O(1)
Hope this helps!

• If you have any questions, please leave a comment below. 💭
  

• If you like this article, please share it with your friends. 💖
  

• If you want to read more articles like this, please follow me.
  

Thank you for reading!