class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& a) {
        vector<vector<int>> ans;
        int n = a.size();
        sort(a.begin(), a.end());
        for (int i = 0; i < n - 2; i ++) {
            int x = a[i];
            if(i && x == a[i - 1]) continue;
            if(x + a[i + 1] + a[i + 2] > 0) break;
            if(x + a[n - 1] + a[n - 2] < 0) continue;
            int j = i + 1, k = n - 1;
            while(j < k) {
                int sum = x + a[j] + a[k];
                if(sum > 0) -- k;
                else if(sum < 0) ++ j;
                else {
                    ans.push_back({x, a[j], a[k]});
                    ++ j;
                    while(j < k && a[j] == a[j - 1]) ++ j;
                    -- k;
                    while(k > j && a[k] == a[k + 1]) -- k;
                }
            }
        }   
        return ans; 
    }
};