15. 3Sum [Leetcode][C++]

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { // Brute Force Solution Time O(N^3) & Auxiliary Space O(1) int len=nums.size(); if(len==0 || len<3) // Atleast three elemnets needed for a triplet return {}; set<vector<int>> s; // Set stores unique elements only(duplicate triplets not added) sort(nums.begin(),nums.end()); // Compare all cases of group of three elements for their sum=0 in O(N^3) time for(int i=0;i<len-2;i++){ for(int j=i+1;j<len-1;j++){ for(int k=j+1;k<len;k++){ if(nums[i]+nums[j]+nums[k]==0){ s.insert({nums[i],nums[j],nums[k]}); } } } } // Insert all unique triplets in result vector vector<vector<int>> ans(s.begin(),s.end()); return ans; } }; 

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums){ // Optimal Solution Time O(N^2) & Auxiliary Space O(1) // Two Pointer Algorithm int len=nums.size(); vector<vector<int>> res; if(len<3) return res; sort(nums.begin(),nums.end()); for(int i = 0; i<len; i++){ if(i>0 && nums[i]==nums[i-1]) // Skip the duplicate elements by incrementing the i index. // 'continue' terminates current iteration and // begins next iteration of for loop continue; // Keeping nums[i] same, check for sum of triplets=0  // from i+1 till the end of nums vector int left = i + 1, right = nums.size() - 1; while(left<right) { if(nums[i] + nums[left] + nums[right] == 0){ res.push_back(vector<int>{nums[i],nums[left],nums[right]}); // To skip duplicate elements at left pointer while(left<right && nums[left]==nums[left+1]) left++; // To skip duplicate elements at left pointer while(left<right && nums[right]==nums[right-1]) right--; // One unique triplet has been found. // Increment left & decrement right for  // next triplet to be unique left++; right--; } // Since nums is sorted, so left will be smallest in  // [nums[left],nums[right]] interval and if triplet sum<0, // then incrementing left will increase the sum else if(nums[i]+nums[left]+nums[right]<0) left++; // Since nums is sorted, so right will be largest in  // [nums[left],nums[right]] interval and if triplet sum>0, // then decrementing right will decrease the sum else right--; } } return res; } };