# LeetCode 3Sum Closest

LeetCode 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    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).

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


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


# LeetCode 3Sum

LeetCode 3Sum
Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, abc)
• 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)

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> tmp;
int min_v = INT_MAX, max_v = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] < min_v) {
min_v = nums[i];
}
if (nums[i] > max_v) {
max_v = nums[i];
}
}
vector<int> hash(max_v - min_v + 1, 0);
for (int i = 0; i < nums.size(); i++) {
hash[nums[i] - min_v]++;
}
for (int i = 0; i < hash.size(); i++) {
if (hash[i] == 0)continue;
hash[i]--;
for (int j = i; j < hash.size(); j++) {
if (hash[j] == 0)continue;
hash[j]--;
int sum1 = i + min_v + j + min_v;
int idx = -sum1 - min_v;
if (idx>=0&&idx<hash.size()&&hash[-sum1 - min_v]) {
vector<int> hit = { i + min_v,j + min_v,-sum1 };
sort(hit.begin(), hit.end());
tmp.insert(hit);
}
hash[j]++;
}
hash[i]++;
}
vector<vector<int>> ans;
for (auto const& vi : tmp) {
ans.push_back(vi);
}
return ans;
}
};


class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> tmp;
if (nums.size() < 3)return tmp;
int min_v = INT_MAX, max_v = INT_MIN;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] < min_v) {
min_v = nums[i];
}
if (nums[i] > max_v) {
max_v = nums[i];
}
}
vector<int> hash(max_v - min_v + 1, 0);
for (int i = 0; i < nums.size(); i++) {
hash[nums[i] - min_v]++;
}
for (int i = 0; i < hash.size(); i++) {
if (hash[i] == 0)continue;
hash[i]--;
int s = i, t = hash.size() - 1;
while (s <= t) {
if (!hash[s]) { s++; continue; }
else { hash[s]--; }
if (!hash[t]) { t--; hash[s]++; continue; }
else { hash[t]--; }
int sum1 = s + min_v + t + min_v;
hash[s]++;
hash[t]++;
if (sum1 + i + min_v < 0) {
s++;
}
else if (sum1 + i + min_v > 0) {
t--;
}
else {
vector<int> hit = { i + min_v,s + min_v,t + min_v };
tmp.push_back(hit);
s++;
t--;
}
}
hash[i]++;
}
return tmp;
}
};


class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
for (int i = 0; i < n; ++i) {
if (i > 0 && nums[i] == nums[i - 1])continue; // avoid duplicates
for (int j = i + 1, k = n - 1; j < k;) {
if (nums[i] + nums[j] + nums[k] == 0) {
ans.push_back({ nums[i],nums[j],nums[k] });
++j;
--k;
while (j < k&&nums[j] == nums[j - 1])++j; // avoid duplicates
while (j < k&&nums[k] == nums[k + 1])--k; // avoid duplicates
} else if (nums[i] + nums[j] + nums[k] > 0) {
--k;
} else {
++j;
}
}
}
return ans;
}
};