3Sum Closest

Given an array A of n integers, find three integers in A such that the sum is closest to a given value. Return the sum of the three integers. You may assume that each input would have exactly one solution.
It is a modified version of the problem 3 Sum

    For example, given array S = {-1 2 1 -4}, and target = 1.

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

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

class Solution { public: int threeSumClosest(vector<int>& nums, int target) { //sort the vector sort(nums.begin(), nums.end()); int temp = 0, j, k, diff = INT_MAX, out = 0; for(int i = 0; i < nums.size(); i++){ j = i + 1; k = nums.size() - 1; while(j < k){ temp = nums[i] + nums[j] + nums[k]; //update the minimum diff till now and store the output if(abs(temp - target) < diff){ diff = abs(temp - target); out = temp; } //if diff is 0, return the output else increment or decrement based on the current (temp - target) value if(diff == 0){ return out; }else if(temp - target < 0){ j++; }else{ k--; } } } return out; } };

Read More

3Sum II

Given an array A of n integers, find all unique triplets in the array which gives the sum of zero.

The problem is a modification of the problem 3 Sum 

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { sort(nums.begin(), nums.end()); vector<vector<int>> result; if(nums.size() < 3) return result; for(int i = 0; i < nums.size() - 2; i++){ if(i == 0 || nums[i] != nums[i - 1]){ int j = i + 1, k = nums.size() - 1; while(j < k){ //use the approach as for 2 Sum if(nums[i] + nums[j] + nums[k] == 0){ vector<int> three; three.push_back(nums[i]); three.push_back(nums[j]); three.push_back(nums[k]); result.push_back(three); j++; k--; // skip duplicates while(j < k && nums[j - 1] == nums[j]){ j++; } // skip duplicates while(j < k && nums[k + 1] == nums[k]){ k--; } } else if(nums[i] + nums[j] + nums[k] < 0){ j++; }else{ k--; } } } } return result; } };

Read More

3 Sum

Given an array and a value, find if there is a triplet in array whose sum is equal to the given value. If there is such a triplet present in array, then print the triplet and return true. Else return false.

Approach:

    1) Sort the input array.

    2) Fix the first element as A[i] where i is from 0 to array size - 2. After fixing the first element of triplet, find the other two elements using the technique used in 2 Sum problem.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68

#include <iostream> using namespace std; void merger(int *arr, int *temp, int low, int mid, int high){ int i, j, k; i = low; j = mid + 1; k = low; while(i <= mid && j <= high){ if(arr[i] <= arr[j]){ temp[k++] = arr[i++]; } else{ temp[k++] = arr[j++]; } } while(i <= mid){ temp[k++] = arr[i++]; } while(j <= high){ temp[k++] = arr[j++]; } for(int i = low; i <=high; i++){ arr[i] = temp[i]; } } void mergeSort(int *arr, int *temp, int low, int high){ if(low < high){ int mid = (low + high) / 2; mergeSort(arr, temp, low, mid); mergeSort(arr, temp, mid + 1, high); merger(arr, temp, low, mid, high); } } int find3Numbers(int *arr, int n, int sum){ int *temp = new int[n]; mergeSort(arr, temp, 0, n - 1); int curSum, left, right; for(int i = 0; i < n - 2; i++){ left = i + 1; right = n - 1; while(left < right){ curSum = arr[i] + arr[left] + arr[right]; if(curSum == sum){ cout << "Triplet : " << arr[i] << " " << arr[left] << " " << arr[right] << " " << endl; return 1; } else if(curSum < sum){ left++; } else{ right--; } } } return 0; } int main(){ int arr[] = {1, 4, 45, 6, 10, 8}; int sum = 51; int n = sizeof(arr)/sizeof(arr[0]); if(find3Numbers(arr, n, sum)){ ; } else{ cout << "No such triplet exists!" << endl; } return 0; }

Read More