DSA/3Sum.cpp at main · mohajit2711/DSA · GitHub

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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
vector<vector<int>> findTriplets(vector<int>arr, int n, int K) {

// Write your code here.

      vector<vector<int>> ans;

   sort(arr.begin() , arr.end());

   int left , right ;

   for(int i = 0 ; i<n ; i++)

   {

       left = i+1 ;

       right = n-1;

       while(left<right)

       {

           if(arr[left]+arr[right]+arr[i] == K)

           {

                ans.push_back({arr[i], arr[left], arr[right]});

               int x = arr[left] ;

               int y = arr[right] ;

               //skipping same elements

               while(left<right && arr[left]==x){

                   left++ ;

               }

                  while(left<right && arr[right]==y){

                   right-- ;

               }

           }

           else if(arr[left]+arr[right]+arr[i] < K){

               left++;

           }

           else{

               right--;

           }

       }

       //skipping same ith element

        while(i+1<n && arr[i]==arr[i+1]){

           i++ ;

       }

   }

   return ans;

}