-
Notifications
You must be signed in to change notification settings - Fork 0
/
3Sum
25 lines (24 loc) · 922 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
// problem url: https://www.codingninjas.com/codestudio/problems/893028?topList=striver-sde-sheet-problems&utm_source=striver&utm_medium=website&leftPanelTab=0
// mode: Medium
// 2 Pointer Algorithm
#include <bits/stdc++.h>
vector<vector<int>> findTriplets(vector<int>arr, int n, int K) {
stable_sort(arr.begin(), arr.end());
vector<vector<int>> ans;
for(int i=0; i<n-2; i++){
int low = i+1, high = n-1;
while(low<high){
if(arr[i] + arr[low] + arr[high] == K){
ans.push_back({arr[i], arr[low++], arr[high--]});
while(low<high && arr[low]==arr[low-1] && ++low);
while(low<high && arr[high]==arr[high+1] && --high);
}else if(arr[i] + arr[low] + arr[high] > K){
--high;
}else{
++low;
}
}
while(i<n && arr[i+1]==arr[i]) ++i;
}
return ans;
}