3SUMs
6 min readDec 11, 2019
2 SUM is classical. I got stuck on 2 SUM a couple of days ago :(. Now when looking back, 2sum is a toy problem.
3 SUM is classical and not that toy.
Classical 3sum: (leetcode 15. 3Sum)
Python solution
TLE solution (n²logn)
Pass 311 test cases and failed for longer lists by getting TLE. One of the fail lists has a length of 3000.
Solution 2 (O(n²), 880 ms )
reference
https://leetcode.com/problems/3sum/discuss/7392/Python-easy-to-understand-solution-(O(n*n)-time).
C++ solutions
Naive solution (TLE O(n³ log n))
//TLE 311 / 313 test cases passed.
// naive O(n^3 log n) algorithm
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
for (int j=i+1; j < n-1; ++j)
{
for(int k = n-1; k> j;--k)
{
auto sum = nums[i] + nums[j] + nums[k];
if(sum==0)
{
ret.insert(vector<int>{nums[i], nums[j], nums[k]});
}
else if(sum>0)
{
continue;
}
else break;
}
}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;
}
};Binary search solution TLE O(n² log n log n)
//TLE 312 / 313 test cases passed.
// O(n^2 log n log n) algorithm by using binary search
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
for (int j=i+1; j < n-1; ++j)
{
int twosum = nums[i] + nums[j];
auto target = -twosum;
if (nums[j+1]<=target && binary_search(nums.begin()+j+1, nums.end(), target))
{
ret.insert(vector<int>{nums[i], nums[j], target});
}
}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;
}
}O(n² log n) algorithm by using binary search + early pruning + unordered_set
//AC 1080 ms.
// O(n^2 log n) algorithm by using binary search
class Solution {
public:
string vector_to_string(vector<int> v){
string ret = "";
for (auto x:v)ret += to_string(x) + '_';
return ret;
}
vector<int> string_to_vector(string s){
vector<int> ret;
string r="";
for(auto c:s)
{
if (c=='_')
{
ret.push_back(stoi(r));
r = "";
}
else r += c;
}
return ret;
}
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
unordered_set<string> ret;
for (int i=0; i < n-2; ++i)
{
// early pruning
if (i > 0 && nums[i]==nums[i-1])continue;
for (int j=i+1; j < n-1; ++j)
{
int twosum = nums[i] + nums[j];
auto target = -twosum;
if (nums[j+1]<=target && binary_search(nums.begin()+j+1, nums.end(), target))
{
ret.insert(vector_to_string(vector{nums[i], nums[j], target}));
}
}
}
vector<vector<int>> fin_ret;
for (auto s: ret)
{
fin_ret.push_back(string_to_vector(s));
}
return fin_ret;
}
};Binary search solution O(n² log n log n) + early pruning: AC
//AC 780 ms.
// O(n^2 log n log n) algorithm by using binary search
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
// early pruning
if (i > 0 && nums[i]==nums[i-1])continue;
for (int j=i+1; j < n-1; ++j)
{
int twosum = nums[i] + nums[j];
auto target = -twosum;
if (nums[j+1]<=target && binary_search(nums.begin()+j+1, nums.end(), target))
{
ret.insert(vector<int>{nums[i], nums[j], target});
}
}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;
}
};Improved solution AC O(n² log n)
// runtime 2548 ms
//time complexity O(n^2 log n)class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
if (nums[i] > 0)break;
int l = i+1, r = n-1;
while (l < r)
{
auto sum = nums[i] + nums[l] + nums[r];
if (sum==0)
{
ret.insert(vector<int>{nums[i], nums[l], nums[r]});
// we have to keep on going, for example
//[-2,0,1,1,2]
// after we get -2, 0, 2, we still need -2, 1, 1
l++; r--;
}
else if(sum > 0)
{
r--;
}
else l++;
}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;
}
};
make it faster by early pruning AC O(n² log n)
// jimmy shen//run time 204 ms
// time complexity: O(n^2 log n). We have log n as we are using a set. Add element has the complexity of O(log n). If we use the unordered_map, we will have the complexity of O(n^2)class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
set<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
if (nums[i] > 0)break;
/**
* The reason that we have the following optimization
* suppose we have two numbers are the same: x, x, y
* then we have 3 cases: 1) x<0 2) x=0 3) x>0
* it's easy to say that x>0 is not OK
* for case 1) and case 2), suppose that we have a pattern x,x,x,x,y,... after carfully analysis, we can get the conclusion that the result based on the first x will contain all the results based on the following repeated x. For example -2, -2, -2, 0, 2, 4. Based on first -2, we can get [(-2, -2, 4), (-2, 0, 2)]. Based on the second -2, we can get [(-2, -2, 4), (-2, 0, 2)]. Based on the third -2, we can get [(-2, 0, 2)]. Hence, we only need collect results based on the first x.
**/
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i+1, r = n-1;
while (l < r)
{
auto sum = nums[i] + nums[l] + nums[r];
if (sum==0)
{
ret.insert(vector<int>{nums[i], nums[l], nums[r]});
// we have to keep on going, for example
//[-2,0,1,1,2]
// after we get -2, 0, 2, we still need -2, 1, 1
l++; r--;
}
else if(sum > 0)
{
r--;
}
else l++;
}
}
vector<vector<int>> fin_ret(ret.begin(), ret.end());
return fin_ret;
}
};
We can improve the above solution to O(n²)
Optimized solution by avoiding repeating AC O(n² )
//run time 92 ms
// time complexity: O(n^2 ).
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
const int n = nums.size();
vector<vector<int>> ret;
for (int i=0; i < n-2; ++i)
{
if (nums[i] > 0)break;
/**
* The reason that we have the following optimization
* suppose we have two numbers are the same: x, x, y
* then we have 3 cases: 1) x<0 2) x=0 3) x>0
* it's easy to say that x>0 is not OK
* for case 1) and case 2), suppose that we have a pattern x,x,x,x,y,... after carfully analysis, we can get the conclusion that the result based on the first x will contain all the results based on the following repeated x. For example -2, -2, -2, 0, 2, 4. Based on first -2, we can get [(-2, -2, 4), (-2, 0, 2)]. Based on the second -2, we can get [(-2, -2, 4), (-2, 0, 2)]. Based on the third -2, we can get [(-2, 0, 2)]. Hence, we only need collect results based on the first x.
**/
if (i > 0 && nums[i] == nums[i-1]) continue;
int l = i+1, r = n-1;
while (l < r)
{
auto sum = nums[i] + nums[l] + nums[r];
if (sum==0)
{
ret.push_back(vector<int>{nums[i], nums[l], nums[r]});
// we have to keep on going, for example
//[-2,0,1,1,2]
// after we get -2, 0, 2, we still need -2, 1, 1
// we also need to aviod repeating [-2,0,0, 1,1,2, 2]
while (l< r && nums[l+1]==nums[l])l++;
while (l< r && nums[r] == nums[r-1])r--;
l++; r--;
}
else if(sum > 0)
{
r--;
}
else l++;
}
}
return ret;
}
};3SUM advanced
solution 1 (O(N + 101³), 304ms)
solution 1 (O(N + 101²), 120ms)
Trick part:
we can infer the third number c from target and a, b.
However, we need kill the over counter as:
if a + b +c = target,
we can get c from a,b and we can also get b from a,c
for example, when target =8, a, b =1,3 we get c=4
when a, b =1,4 , we get c =3. This will generate over counting.
Using a seen set to kill to over counting.
16. 3Sum Closest
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
const int n = nums.size();
int ret = nums[0] + nums[1] + nums[2];
for (int i = 0; i < n - 2; ++i){
int l = i + 1, r = n - 1;
while (l < r){
int threeSum = nums[i] + nums[l] + nums[r];
if (abs(threeSum - target) < abs(ret - target)) ret = threeSum;
if (threeSum > target) r--;
else if (threeSum < target) l++;
else return target;
}
}
return ret;
}
};Reference
https://leetcode.com/problems/3sum/discuss/232712/Best-Python-Solution-(Explained)
