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, a ≤ b ≤ c)
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)

主要在去重方面走了弯路。思路同Two sum.

从num中取出一个数，就要把它的所有和为0的组合找出来。

找到一组之后，找下一组，i++,j--，但是要注意去重。

取出一个数的时候，就从它后面开始找其他两个数，因为在他之间的数已经找过了。 i = k + 1;

确定范围之后，下一个k必须要忽略相同的数（Line 12) num[k] != num[k+1],k++。

    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > ret;
        if (num.size() < 3) return ret;
        
        vector<int> v;
        sort(num.begin(), num.end());
        
        for (int k = 0; k < num.size(); ++k) {
            // get num[k], search in [k + 1, n - 1]
            int i = k + 1, j = num.size() - 1;
            
            // ignore duplicate num[k]
            while (k < num.size() - 1 && num[k] == num[k + 1]) k++;
            
            while (j > i) {
                int s = num[i] + num[j];

                if (s == -num[k]) {
                    v.push_back(num[i]);
                    v.push_back(num[k]);
                    v.push_back(num[j]);
                    sort(v.begin(), v.end());
                    ret.push_back(v);
                    v.clear();
                    
                    // continue to find another match
                    i++;
                    while (i <= j && num[i] == num[i - 1]) i++;
                    j--;
                    while (j >= i && num[j] == num[j + 1]) j--;
                } else if (s > -num[k]) {
                    j--;
                } else {
                    i++;
                }
            }
        }
        
        return ret;
    }

写得简洁一点。

class Solution {
public:
    vector<vector<int> > threeSum(vector<int> &num) {
        vector<vector<int> > ans;
        if (num.empty()) return ans;
        sort(num.begin(), num.end());
        int n = num.size();
        for (int i = 0; i + 2 < n; ) {
            int target = -num[i]; 
            for (int j = i + 1, k = n - 1; j < k; ) {
                int sum = num[j] + num[k];
                if (sum == target) { // sum + num[i] == 0
                    vector<int> tmp = {num[i], num[j], num[k]};
                    sort(tmp.begin(), tmp.end());
                    ans.push_back(tmp);
                    for (++j; j < k && num[j] == num[j - 1]; ++j); // ignore dups
                    for (--k; k > j && num[k] == num[k + 1]; --k);
                } else if (sum < target) {
                    j++;
                } else {
                    k--;
                }
            }
            for (++i; i + 2 < n && num[i] == num[i - 1]; ++i);
        }
        
        return ans;
    }
};

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

和3 sum类似，就是在查找的时候，必须跟踪最小的差值。

class Solution {
public:
    int threeSumClosest(vector<int> &num, int target) {
        if (num.size() < 3) return INT_MAX;
        
        sort(num.begin(), num.end());
        int minDiff = INT_MAX, minSum = target;
        for (int k = 0; k < num.size(); ++k) {
            // get num[k], search in [k + 1, n - 1]
            int i = k + 1, j = num.size() - 1;
            
            int t = target - num[k]; 
            
            while (j > i) {
                int s = num[i] + num[j];
                if (abs(s - t) < minDiff) {
                    minDiff = abs(s - t);
                    minSum = s + num[k];
                }
                if (s == t) {
                    return target;
                } else if (s > t) {
                    j--;
                } else {
                    i++;
                }
            }
            
            // ignore duplicate num[k]
            while (k < num.size() - 1 && num[k] == num[k + 1]) k++;
        }
        
        return minSum;
    }
};

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:
Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
The solution set must not contain duplicate quadruplets.
For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

A solution set is:
(-1, 0, 0, 1)
(-2, -1, 1, 2)
(-2, 0, 0, 2)

3 sum类似，加了一层。244ms.

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > ret;
        if (num.size() < 4) return ret;
        
        vector<int> v;
        sort(num.begin(), num.end());
        
        for (int m = 0; m < num.size(); ++m) {
            for (int k = m + 1; k < num.size(); ++k) {
                // get num[k], search in [k + 1, n - 1]
                int i = k + 1, j = num.size() - 1;
                int t = target - num[m] - num[k];
                // ignore duplicate num[k]
                while (k < num.size() - 1 && num[k] == num[k + 1]) k++;
                
                while (j > i) {
                    int s = num[i] + num[j];
    
                    if (s == t) {
                        v.push_back(num[m]);
                        v.push_back(num[k]);
                        v.push_back(num[i]);
                        v.push_back(num[j]);
                        sort(v.begin(), v.end());
                        ret.push_back(v);
                        v.clear();
                        
                        // continue to find another match
                        i++;
                        while (i <= j && num[i] == num[i - 1]) i++;
                        j--;
                        while (j >= i && num[j] == num[j + 1]) j--;
                    } else if (s > t) {
                        j--;
                    } else {
                        i++;
                    }
                }
            }
            while (m < num.size() - 1 && num[m] == num[m + 1]) m++;
        }
        return ret;
    }
};

4 sum有O(n^2)的解法，leetcode的discuss后面有。但是那个代码760ms。按照同样的思路，用set来去重，也是760ms。

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > ret;
        if (num.size() < 4) return ret;
        
        sort(num.begin(), num.end());
        
        map<int, vector<pair<int, int> > > sums;
        
        for (int i = 0; i < num.size(); ++i) {
            for (int j = i + 1; j < num.size(); ++j) {
                sums[num[i] + num[j]].push_back(pair<int, int>(i, j));
            }
        }
        
        map<int, vector<pair<int, int> > >::iterator it;
        vector<int> v;
        set<vector<int> > r;
        for (int i = 0; i < num.size(); ++i) {
            for (int j = i + 1; j < num.size(); ++j) {
                int s = target - num[i] - num[j];
                if ((it = sums.find(s)) != sums.end()) {
                    for (vector<pair<int, int>>::iterator it2 = it->second.begin(); 
                            it2 != it->second.end(); ++it2) {
                        if (it2->first <= j) continue;
                        v.push_back(num[i]);
                        v.push_back(num[j]);
                        v.push_back(num[it2->first]);
                        v.push_back(num[it2->second]);
                        r.insert(v);
                        v.clear();
                    }
                }
            }
        }
        
        for (set<vector<int> >::iterator it = r.begin(); it != r.end(); it++) {
            ret.push_back(*it);
        }
        return ret;
    }
};