Given an array of n integers and an integer “key”, find three integers in the array such that the sum is closest to key.

Input: [-1, 2, 1, -4]  Key = 1

Output:

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2)

Below are the steps that we can arrive at the solution.

Step 1: Sort the array.

Step 2: Take an initial integer “closest_sum” that stores the value of the first 3 numbers from the array.

closest_sum = arr[0] + arr[1] + arr[2]

This variable stores the final result.

Step 3: Take a for loop, that starts from the starting of the array.

Now we have to find 2 integers whose sum is closest to the key value.

Hence this problem is similar to the two sum problem.

Now we take 2 pointers, left_pointer starting from the beginning of the array, then the right_pointer from the end of the array.

Then we add those elements present in the index, if the sum is less than the current “closest_sum”, then we have to update with the new value.

The above step 3 can be programmatically written as below:

for (int i = 0 to array_length -1 ) 
{            
    left_pointer = i + 1;
    right_pointer = array_length - 1;
            
         while (left_pointer < right_pointer) 
        {
            sum = nums[i] + nums[left_pointer] + nums[right_pointer];
            if (abs(sum - target) < abs(closetSum - target)) // to find the closest sum we use this formula
            {
                closetSum = sum; // update the closest sum
            }
            if (sum < target)
            {
                insrement left_pointer
            } 
            else 
            {
                decrement right_pointer
            }
        }
 } 

Let us understand with the help of an example.

We take a sorted array [-4, -1, 1, 2] and key = 1

closest_sum =. -4 -1 + 1 = -4

Pass 1 of for loop:
	i = 0
	left_pointer = 1
	Right_pointer = 3

	Pass 1 of while loop
		1 < 3
			sum = -4 -1 +2 = -3
				if (4 < 5)
					closest_sum = -3

				if (-3 < 1)
					true
						increment left_pointer

	Pass 2 of while loop
		2 < 3
			sum = -4 + 1 +2 = -1
				if (2 < 4)
					closest_sum = -1

				if (-1 < 2)
					true
						increment left_pinter.

	Pass 3 of while loop:

		3 < 3 false

Pass 2 of for loop:
	i = 1
	left_pointer = 2
	Right_pointer = 3

	Pass 1 of while loop
		2 < 3
			sum = -1 + 1 +2 = 2
				if (1 < 2)
					closest_sum = 2


Hence our result is "2"

Solution in C++

#include<iostream>
#include<vector>
using namespace std;

void threeSumClosest (vector<int> &arr, int key)
{
	sort(arr.begin(), arr.end());

	int closest_sum = arr[0] + arr[1] + arr[2];
    int len = arr.size();


    for (int i = 0; i <= len - 3; i++) 
    {
   		int left_pointer 	= i + 1;  
   		int right_pointer 	= len - 1;

       	while (left_pointer < right_pointer) 
       	{
        	int sum = arr[i] + arr[left_pointer] + arr[right_pointer];

            if (abs(sum - key) < abs(closest_sum - key))
            	closest_sum = sum;


                if (sum < key) 
                {
                   left_pointer ++;
                } else if (sum > key) 
                {
                    right_pointer--;
                } 
            }
        }
        
        cout<< "The closest to the key "<< key << " is = "<< closest_sum << endl;
}

int main() {
    
    vector<int> arr;
    int key = 1;

	arr.push_back(-1);
	arr.push_back(2);
	arr.push_back(1);
	arr.push_back(4);

	threeSumClosest(arr, key);

    return 0;
}

Output:

The closest to the key 1 is = 2

List Of Tutorials available in this website: