YEZAELP

LeetCode: 3Sum

Oct 29th, 2021 (edited)
1,072
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. class Solution {
  2. public:
  3.  
  4.     using pi = pair <int, int>;
  5.     vector < vector <int>> ans;
  6.     int pos[200010], neg[200010], zero;
  7.     pi piz = {0, 0};
  8.    
  9.     vector<vector<int>> threeSum(vector<int>& nums) {
  10.         int len = nums.size();
  11.  
  12.         if(len < 3) return ans;
  13.  
  14.         sort(nums.begin(), nums.end());
  15.  
  16.         for(auto i: nums){
  17.             if(i == 0) zero ++;
  18.             else if(i > 0) pos[i] ++;
  19.             else neg[-i] ++;
  20.         }
  21.  
  22.         for(int i=0;i<len;i++){
  23.             for(int j=i+1;j<len;j++){
  24.                 int a = nums[i], b = nums[j], c = a + b;
  25.                 if(a < 0 and b < 0 and pos[-c] != 0){
  26.                     ans.push_back({a, b, -c});
  27.                 }
  28.                 if(a > 0 and b > 0 and neg[c] != 0){
  29.                     ans.push_back({-c, a, b});
  30.                 }
  31.             }
  32.         }
  33.  
  34.         if(zero >= 1){
  35.             for(int i=1;i<=100000;i++){
  36.                 if(pos[i] != 0 and neg[i] != 0)
  37.                     ans.push_back({-i, 0, i});
  38.             }
  39.         }
  40.  
  41.         if(zero >= 3) ans.push_back({0, 0, 0});
  42.            
  43.         sort(ans.begin(), ans.end());
  44.        
  45.         ans.resize( unique(ans.begin(), ans.end()) - ans.begin() );
  46.        
  47.         return ans;
  48.     }
  49. };
RAW Paste Data Copied