forked from MukulCode/CodingClubIndia
-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy path3sumClosestProblem.cpp
More file actions
53 lines (48 loc) · 1.4 KB
/
3sumClosestProblem.cpp
File metadata and controls
53 lines (48 loc) · 1.4 KB
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
#include <bits/stdc++.h>
using namespace std;
/*
Question:-
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.
*/
int threeSumClosest(vector<int> &nums, int target)
{
sort(nums.begin(), nums.end());
int ans = INT_MAX;
int isNeg = 1;
int low, high, i, t, n = nums.size();
for (i = 0; i < n - 2; i++)
{
if (i == 0 || nums[i] > nums[i - 1])
{
low = i + 1, high = n - 1, t = target - nums[i];
while (low < high)
{
int temp = target - (nums[low] + nums[high] + nums[i]);
if (nums[low] + nums[high] == t)
{
return target;
}
else if (nums[low] + nums[high] > t)
high--;
else
low++;
if (temp < 0 && ans > (-1 * temp))
ans = min(ans, -1 * temp), isNeg = 1;
else if (temp > 0 && ans > temp)
ans = min(ans, temp), isNeg = -1;
}
}
}
return target + ans * isNeg;
}
int main()
{
int n,target;
cin>>n>>target;
vector<int> nums(n);
for(int i=0;i<n;i++)
cin>>nums[i];
cout<<threeSumClosest(nums,target);
}