https://leetcode.com/problems/3sum/

1. Brute force(Time Limit Exceeded):

  1. //TLE
  3. class Solution {
  4. public:
  5.     vector<vector<int>> threeSum(vector<int>& nums) {
  6.         vector<vector<int>> result;
  8.         if(nums.empty())
  9.             return result;
  11.         if(nums.size() <= 2)
  12.             return result;
  14.         int len = nums.size();
  15.         int last = 2;
  17.         for(int L = 0; L < len - 2; L++){
  18.             for(int R = L + 1; R < len - 1; R++){
  19.                 last = R + 1;
  20.                 while(last < len){
  21.                     if(nums[last] == 0 - (nums[L] + nums[R])){
  22.                         vector<int> curr;
  23.                         curr.push_back(nums[L]);
  24.                         curr.push_back(nums[R]);
  25.                         curr.push_back(nums[last]);
  26.                         sort(curr.begin(), curr.end());
  27.                         result.push_back(curr);
  28.                     }    
  29.                     last++;
  30.                 }
  31.             }
  32.         }
  34.         sort(result.begin(), result.end());
  35.         result.erase(unique(result.begin(), result.end()), result.end());
  37.         return result;
  38.     }
  39. };

2. Two pointers:

  1. //124 ms    19.6 MB
  3. class Solution {
  4. public:
  5.     vector<vector<int>> threeSum(vector<int>& nums) {
  6.         vector<vector<int>> result;
  8.         if(nums.empty())
  9.             return result;
  11.         if(nums.size() <= 2)
  12.             return result;
  14.         sort(nums.begin(), nums.end());
  16.         int n = nums.size();
  18.         for(int i = 0; i < n - 2; ++i) {
  19.             if (nums[i] > 0) break; // because sorted, first is positive -> not a set
  21.             if (i > 0 && nums[i] == nums[i - 1]) //duplicates
  22.                 continue;
  24.             int l = i + 1;
  25.             int r = n - 1;
  27.             while (l < r) {
  28.                 if (nums[l] + nums[i] + nums[r] == 0) {
  29.                     result.push_back({nums[l], nums[i], nums[r]});
  30.                     l++;
  31.                     r--;
  33.                     while (l < r && nums[l] == nums[l - 1]) //duplicates
  34.                         l++;
  35.                     while (l < r && nums[r] == nums[r + 1]) //duplicates
  36.                         r--;          
  37.                 } else if (nums[i] + nums[l] + nums[r] < 0) {
  38.                   l++;
  39.                 } else {
  40.                   r--;
  41.                 }
  42.             }
  43.         }
  44.         return result;
  45.     }
  46. };

Time complexity: O(n log(n) + n^2)
Space complexity: O(1)