jayati

Find All Four Sum Numbers

Sep 12th, 2023
956
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.85 KB | None | 0 0
  1. vector<vector<int> > fourSum(vector<int> &arr, int k) {
  2.         // Your code goes here
  3.         sort(arr.begin(),arr.end());
  4.        
  5.         vector<vector<int>>ans;
  6.         for(int i=0 ; i<arr.size() ; i++)
  7.         {
  8.             if(i>0 && arr[i]==arr[i-1])
  9.             {
  10.                 continue;
  11.             }
  12.             for(int j=arr.size()-1 ; j>=i+3 ; j--)
  13.             {
  14.                 if(j<arr.size()-1 && arr[j]==arr[j+1])
  15.                 {
  16.                     continue;
  17.                 }
  18.                 int low =i+1;
  19.                 int high=j-1;
  20.                 while(low<high)
  21.                 {
  22.                    
  23.                     int sum=arr[i]+arr[j]+arr[low]+arr[high];
  24.                     if(sum==k)
  25.                     {
  26.                         ans.push_back({arr[i],arr[low],arr[high],arr[j]});
  27.                         while(arr[low]==arr[low+1])
  28.                         {
  29.                             low++;
  30.                         }
  31.                         low++;
  32.                         while(arr[high]==arr[high-1])
  33.                         {
  34.                             high--;
  35.                         }
  36.                         high--;
  37.                     }
  38.                     else if(sum<k)
  39.                     {
  40.                         while(arr[low]==arr[low+1])
  41.                         {
  42.                             low++;
  43.                         }
  44.                         low++;
  45.                     }
  46.                     else{
  47.                         while(arr[high]==arr[high-1])
  48.                         {
  49.                             high--;
  50.                         }
  51.                         high--;
  52.                     }
  53.                 }
  54.             }
  55.         }
  56.         sort(ans.begin(),ans.end());
  57.         return ans;
  58.    }
  59. // https://practice.geeksforgeeks.org/problems/find-all-four-sum-numbers1732/
Advertisement
Add Comment
Please, Sign In to add comment