学步园

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)

算法一，在3sum基础上，再套上一层循环。时间复杂度为O(n^3)

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        vector<vector<int> > result;
        if (num.size() < 4) return result;

        sort(num.begin(), num.end());
        for (int i=0; i< num.size(); i++) {
                if (i && num[i] == num[i-1])
                        continue;

                for (int j=i+1; j<num.size(); j++) {
                        if (j>i+1 && num[j] == num[j-1])
                                continue;

                        int p = j+1, q = num.size()-1;
                        while (p < q) {
                                const int sum = num[i] + num[j] + num[p] + num[q];
                                if (sum == target) {
                                        vector<int> b;
                                        b.push_back(num[i]);
                                        b.push_back(num[j]);
                                        b.push_back(num[p]);
                                        b.push_back(num[q]);
                                        result.push_back(b);
                                        while (++p < q && num[p] == num[p-1]);
                                        while (--q > p && num[q] == num[q+1]);
                                }
                                else if (sum < target)
                                        ++p;
                                else
                                        --q;
                        }

                }
        }

        return result;
    }
};

算法2: 利用hash查找。时间复杂度O(n^2 log n)。

此算法时间复杂度要优于算法1。表面上看起来，它的运行速度也会快于算法1.

但实则不然，在leetcode上，统计显示，此算法时间已经沦为用java或者python的时间范围内。远不如算法1快。

这可能是因为它存在大量的内存分配请求和内存拷贝的原因，而导致它比算法1慢。

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        sort(num.begin(), num.end());
        set<vector<int> > result;
        unordered_map<int, set<pair<int, int> > > hash;
        for (int i=0; i<num.size(); i++) {
                for (int j=i+1; j<num.size(); j++) {
                        if (j>i+1 && num[j] == num[j-1])
                                continue;

                        const auto iter = hash.find(target-num[i]-num[j]);
                        if (iter != hash.end()) {
                                for (auto &p: iter->second) {
                                        vector<int> b = {p.first, p.second, num[i], num[j]};
                                        result.insert(b);
                                }
                        }
                }

                for (int j=0; j<i; j++) {
                        if (!j || num[j] != num[j-1])
                                hash[num[j]+num[i]].insert(make_pair(num[j], num[i]));
                }
        }
        return vector<vector<int> >(result.begin(), result.end());
    }
};