[LeetCode] 4sum

 

 

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
         sort(num.begin(),num.end());
         vector<vector<int> > res;
         int* a = &num[0];
         int len = num.size();
         for (int i = 0; i < len; i++) {
             if (i > 0 && num[i] == num[i-1]) continue;
             for (int j = i+1; j < len; j++) {
                 if (j > i+1 && num[j] == num[j-1]) continue;
                 int x = j+1, y = len - 1;
                 while (x < y) {
                     int t = a[i] + a[j] + a[x] + a[y];
                     if (t == target) {
                         res.push_back({a[i], a[j], a[x], a[y]});
                         while (x < y && a[x+1] == a[x]) x++;
                         while (x < y && a[y-1] == a[y]) y--;
                         x++; y--;
                     } else if (t > target) {
                         y--;
                     } else {
                         x++;
                     }
                 }
             }
         }
         return res;
    }
};

 

 

@2013-10-07

N3

写了个复杂版本的。好处是方便拓展sum(a1...ai)都可以。i=2，3，4，5...

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > res;
        int n = num.size();
        if (n < 4) return res;
        sort(num.begin(), num.end());
        vector<int> v;
        gen(num, res, v, target, 0, 4);
        return res;
    }
    
    void gen(const vector<int>& a,vector<vector<int> >&res, vector<int>& v, int tar, int cur, int total) {
        if (v.size() == total) return;
        if (total - v.size() == 2) {
            int i = cur, j = a.size() - 1;
            while (i < j) {
                if (a[i] + a[j] == tar) {
                    v.push_back(a[i]);
                    v.push_back(a[j]);
                    res.push_back(v);
                    v.pop_back();
                    v.pop_back();
                    int t = i;
                    while (i < j && a[i] == a[t]) i++;
                    t = j;
                    while (i < j && a[j] == a[t]) j--;
                }
                else if (a[i] + a[j] > tar) j--;
                else i++;
            }
            return;
        }
        int prev, i = cur;
        while (i + 3 - v.size() < a.size()) {
            v.push_back(a[i]);
            gen(a, res, v, tar - a[i], i+1, total);
            v.pop_back();
            prev = i;
            while (i < a.size() && a[prev] == a[i]) i++;
        }
    }
};