leetcode-jecklee/4Sum.cpp at master · rainlee/leetcode-jecklee · GitHub

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
/***
 * 先排序，后左右夹逼
 * 三层循环，可以直接调用3Sum
 * 时间复杂度O(n^3)
 * 注意去重
 ***/
class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        const int n = num.size();

        std::sort(num.begin(), num.end());  // sort first!!!

        for (int i = 0; i < n-3; ++i)
        {
            if ((i > 0) && (num[i] == num[i-1]))
                continue;
            threeSum(num, i, target);
        }
        return vvnums;
    }
private:
    vector<vector<int> > vvnums;

    void twoSum(vector<int> &num, int i1, int i2, int target)
    {
        vector<int> vret(4);
        vret[0] = num[i1];
        vret[1] = num[i2];

        int low = i2 + 1;
        int high = num.size() - 1;

        while (low < high)
        {
            int sum = num[i1] + num[i2] + num[low] + num[high];

            if (sum == target)
            {
                vret[2] = num[low];
                vret[3] = num[high];

                vvnums.push_back(vret);

                while ((num[++low] == num[low-1]) && (low < high)) ;
                while ((num[--high] == num[high+1] && (low < high)));
            }
            else if (sum > target)
                --high;
            else
                ++low;
        }
        return;
    }
    void threeSum(vector<int> &num, int i1, int target)
    {
        for (int i = i1+1; i < num.size()-2; ++i)
        {
            if ((i > i1+1) && (num[i] == num[i-1]))
                continue;
            twoSum(num, i1, i, target);
        }
        return;
    }
};