# LeetCode 3Sum Closest

Given an array nums of n integers 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:

Given array nums = [-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

Given an array nums of n integers, are there elements abc in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-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;
}
};

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>> ans;
int n = nums.size();
unordered_map<int, int> hash;
for(int i = 0; i < n; ++i) ++hash[nums[i]];
for(int i = 0; i < n; ++i) {
if(i != 0 && nums[i] == nums[i - 1]) continue;

--hash[nums[i]];
for(int j = i + 1; j < n; ++j) {
if(j != i + 1 && nums[j] == nums[j - 1]) continue;

--hash[nums[j]];
int another = - nums[i] - nums[j];
if(another >= nums[j] && hash[another] > 0) ans.push_back({nums[i], nums[j], another});
++hash[nums[j]];
}
++hash[nums[i]];
}
return ans;
}
};

class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());

vector<vector<int>> ans;
int n = nums.size();
int i = 0;
while(i < n - 2) {
if(i != 0 && nums[i] == nums[i - 1]) {
++i;
continue;
}
int target = -nums[i];
int j = i + 1, k = n - 1;
while(j < k) {
if(nums[j] + nums[k] == target) {
vector<int> tmp = {nums[i], nums[j], nums[k]};
ans.push_back(tmp);
while(j < k && nums[j] == tmp[1]) ++j;
while(j < k && nums[k] == tmp[2]) --k;
} else if (nums[j] + nums[k] > target) {
--k;
} else {
++j;
}
}
++i;
}
return ans;
}
};