Share my C++ solution, 46ms, O(N^2)


  • 0
    Y
    class Solution {
    public:
      vector<vector<int>> threeSum(vector<int>& a) {
        vector<vector<int>> res;
        int n = a.size(), i = 0;
        if (n<3) return res;
        sort(a.begin(), a.end());
        while(true) {
          int j=i+1, k=n-1, s=-a[i];
          while(j<k) {
            while (k>j+1 && a[j]+a[k]>s) k--;
            if (a[j]+a[k]==s)
              res.push_back(vector<int> {-s, a[j], a[k]});
            while (a[j]==a[++j] && j<k);
          }
          while (a[i]==a[++i] && i<j-1);
          if (i==j-1) break;
        }
        return res;
      }
    };

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.