[leetcode_15]3Sum

Want to know why I almost gave up later? It was because I got stuck on the 3Sum problem, which prevented me from picking high-acceptance-rate problems to work on. The 3Sum problem also kept giving me OLE!

The 3Sum problem asks: given a sequence, find all triplets whose sum equals zero.

At first I naively thought it would be as simple as the 2Sum problem with a greedy two-pointer approach. But no.

My approach:

Sort the array in O(n log n)
Enumerate three cases: two negatives and one positive, three zeros, one negative and two positives
O(n^2) complexity, using binary search for the third number

This should actually be faster than strict O(n^2).

I was worried about TLE from the start. But instead it gave me Output Limit Exceeded – so frustrating.

After modifying the code, finally Accepted:

  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;
        }
        //two negatives and one positive
        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);
                }
            }
        }
        //three zeros
        if(count0 >= 3) {
            vector<int> ivector(3, 0);
            ans.push_back(ivector);
        }
        //one negative and two positives
        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);
        }
    }
};