Leetcode/4sum.h at master · bluepp/Leetcode · 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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
/*
 bluepp

 2014-05-28
 2014-07-05
 2014-08-03
 2014-08-29
 2014-09-20

 May the force be with me!


 Problem:    4Sum
 Difficulty: Medium
 Source:    https://oj.leetcode.com/problems/4sum/
 Notes:
 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:
 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)

 Solution: Similar to 3Sum, 2Sum.
 */


/* 2014-09-20, my version */

    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());

        for (int i = 0; i < n-3; i++)
        {
            if (i > 0 && num[i] == num[i-1]) continue;

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

                int l = j+1, r = n-1;

                while (l < r)
                {
                    int tmp = num[i]+num[j]+num[l]+num[r];

                    if (tmp == target)
                    {
                        vector<int> vec;

                        vec.push_back(num[i]);
                        vec.push_back(num[j]);
                        vec.push_back(num[l]);
                        vec.push_back(num[r]);

                        res.push_back(vec);

                        while (num[l] == num[l+1]) l++;
                        while (num[r] == num[r-1]) r--;

                        l++;
                        r--;
                    }
                    else if (tmp < target)
                    {
                        l ++;
                    }
                    else
                    {
                        r--;
                    }
                }
            }
        }

        return res;
    }


    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());

        for (int i = 0; i < n-3; i++)
        {
            if (i > 0 && num[i] == num[i-1]) continue;
            for (int j = i+1; j < n-2; j++)
            {
                if (j > i+1 && num[j] == num[j-1]) continue;

                int l = j+1, r = n-1;
                while (l < r)
                {
                    int tmp = num[i] + num[j] + num[l] + num[r];
                    if (tmp == target)
                    {
                        vector<int> vec;
                        vec.push_back(num[i]);
                        vec.push_back(num[j]);
                        vec.push_back(num[l]);
                        vec.push_back(num[r]);
                        res.push_back(vec);

                        while (l > 0 && num[l] == num[l+1]) l++;
                        while (r < n-1 && num[r] == num[r-1]) r--;

                        l++; r--;
                    }
                    else if (tmp < target) l++;
                    else r--;
                }
            }
        }

        return res;

    }