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
132
133

#include <algorithm>

using namespace std;
int cmp(int a,int b) {
    return a < b;
}
class Solution {
public:
    vector<vector<int>> threeSum(vector<int> &num) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        vector<vector<int>> ans;
        ans.clear();
        int *seq = new int[num.size()];
        for(int i = 0; i < num.size(); i++) {
            seq[i] = num[i];
        }
        sort(seq, seq + num.size(), cmp);
        int count0 = 0;
        int left = -1;
        int right = -1;
        for(int i = 0; i < num.size(); i++) {
            if(seq[i] == 0) {
                if(left == -1) {
                    left = i - 1;
                }
                count0++;
            }
            if(seq[i] > 0) {
                if(left == -1) {
                    left = i - 1;
                }
                if(right == -1) {
                    right = i;
                    break;
                }
            }
        }
        int index = 0;
        if(left == -1 || right == -1) {
            if(count0 >= 3) {
                vector<int> ivector(3, 0);
                ans.push_back(ivector);
            }
            return ans;
        }
        //两负一正
        for(int i = 0; i < left; i++) {
            for(int j = i + 1; j <= left; j++) {
                int a[3];
                a[0] = seq[i];
                a[1] = seq[j];
                a[2] = (seq[i] + seq[j]) * (-1);
                if(bsearch(right, num.size() - 1, seq, a[2]) == true) {
                    vector<int> ivector(a, a + 3);
                    bool flag = false;
                    for(int k = 0; k < ans.size(); k++) {
                        if(ivector == ans[k]) {
                            flag = true;
                            break;
                        }
                    }
                    if(flag == false)
                        ans.push_back(ivector);
                }
            }
        }
        if(count0 >= 1) {
            for(int i = 0; i <= left; i++) {
                if(i >= 1) {
                    if(seq[i] == seq[i - 1])
                        continue;
                }
                int a[3];
                a[0] = seq[i];
                a[1] = 0;
                a[2] = seq[i] * (-1);
                if(bsearch(right, num.size() - 1, seq, a[2]) == true) {
                    vector<int> ivector(a, a + 3);
                    bool flag = false;
                    for(int k = 0; k < ans.size(); k++) {
                        if(ivector == ans[k]) {
                            flag = true;
                            break;
                        }
                    }
                    if(flag == false)
                        ans.push_back(ivector);
                }
            }
        }
        //三个零
        if(count0 >= 3) {
            vector<int> ivector(3, 0);
            ans.push_back(ivector);
        }
        //一负两正
        for(int i = right; i < num.size() - 1; i++) {
            for(int j = i + 1; j < num.size(); j++) {
                if(i != j) {
                    int a[3];
                    a[1] = seq[i];
                    a[2] = seq[j];
                    a[0] = (seq[i] + seq[j]) * (-1);
                    if(bsearch(0, left, seq, a[0]) == true) {
                        vector<int> ivector(a, a + 3);
                        bool flag = false;
                        for(int k = 0; k < ans.size(); k++) {
                            if(ivector == ans[k]) {
                                flag = true;
                                break;
                            }
                        }
                        if(flag == false)
                            ans.push_back(ivector);
                    }
                }
            }
        }       
        return ans;
    }
    bool bsearch(int left, int right, int *num, int a) {
        if(left > right)
            return false;
        int mid = (left + right) / 2;
        if(num[mid] == a) return true;
        if(num[mid] > a) {
            return bsearch(left, mid - 1, num, a);
        }
        if(num[mid] < a) {
            return bsearch(mid + 1, right, num, a);
        }
    }
};