3Sum Closest

Problem 3 Closest Sum
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).

The idea that a lot of people will think of is to brute force all the possible 3 combinations of integers in the nums array sum them and return the closest one.
This solution works but comes with a cost which is the high time complexity of O(n^3)

There is a better way to do it, yes there is.
Using the two pointer technique.
Read about two pointer technique

First Sort the array of nums.
the time complexity of the sorting nums is nlog(n)

declare the maxSum = 0

Then loop through the array from 0 to n-2.

Declare the two pointers
l = i + 1
r = n -1
loop while l < r
calculate the sum as nums[i] + nums[l] + nums[r]

check if i = 0 sum > 0;
reassign maxSum = sum

check if sum == target
if yes return sum

check if sum is closer than previous sum;
if sum > 0
check if target-sum < target-maxSum
if yes maxSum = sum
else sum < 0
target-sum > target -maxSum
maxSum = sum

Next is to move the pointer

if sum < target
increment l pointer

if sum > target
decrement r counter

and hence you don't have to bother about missing the values because the array is sorted.
nums[r] pointer is the max value hence you decrease r pointer to reduce the sum, and check again.

else if sum is less than target nums[l] pointer is the smallest and hence you increment the counter value, l=l+1, nums[l+1] which is larger than nums[l] hence you decrease in other to check for l+1.
until l == r.
Then you increment break out inner loop and continue to the first loop by incrementing i.
set l to i+1
set r to n-1.
Repeat the process
And when you get to i = n-2. Repeat the process stop and
Return MaxSum.
Given the time complexity as nlog(n) + O(n^2).
We take the max And the overall time complexity is O(n^2)
with O(1) space complexity.