forked from Kritika-byte/DSA-for-k
-
Notifications
You must be signed in to change notification settings - Fork 0
/
3Sum
28 lines (27 loc) · 999 Bytes
/
3Sum
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<vector<int>>res;
for(int i=0;i<nums.size()-2;i++){
if(i==0||(i > 0 && nums[i] != nums[i-1])){
int lo=i+1, hi =nums.size()-1,sum=0-nums[i];
while(lo<hi){
if(nums[lo]+nums[hi]==sum){
vector<int>temp;
temp.push_back(nums[i]);
temp.push_back(nums[lo]);
temp.push_back(nums[hi]);
res.push_back(temp);
while(lo<hi && nums[lo]==nums[lo+1]) lo++;
while(lo<hi && nums[hi]==nums[hi-1]) hi--;
lo++; hi--;
}
else if (nums[lo]+nums[hi]<sum) lo++;
else hi--;
}
}
}
return res;
}
};