3 different ways of solving 3sum


  • 0
    B

    First solution (simple: O(n^3))
    run three loops and check one by one that sum of three elements is zero or not if sum of three elements is zero then print elements.

    void findTriplets(int arr[], int n){
        for (int i=0; i<n-2; i++){
            for (int j=i+1; j<n-1; j++){
                for (int k=j+1; k<n; k++){
                    if (arr[i]+arr[j]+arr[k] == 0){
                        cout << arr[i] << " "<< arr[j] << " "<< arr[k] <<endl;
                    }
                }
            }
        }
    }
    

    Second solution (hashing: O(n^2))

    1. Run a loop from i=0 to n-2
    2. Create an empty hash table
    3.  Run inner loop from j=i+1 to n-1
          If -(arr[i] + arr[j]) is present in hash table
             print arr[i], arr[j] and -(arr[i]+arr[j])
          Else
             Insert arr[j] in hash table.
    

    code:

    void findTriplets(int arr[], int n){
     
        for (int i=0; i<n-1; i++){
           
            unordered_set<int> s;
    
            for (int j=i+1; j<n; j++){
                int x = -(arr[i] + arr[j]);
                if (s.find(x) != s.end())
                    cout<<x<<" "<<arr[i]<<" "<<arr[j]<<endl;
                
                else
                    s.insert(arr[j]);
            }
        }
     }
    

    Third solution (sorting: O(n^2))
    it's something like binary search.

    1. Sort all element of array
    2. Run loop from i=0 to n-2.
         Initialize two index variables l=i+1 and r=n-1
    4. while (l < r) 
         Check sum of arr[i], arr[l], arr[r] is
         zero or not if sum is zero then print the
         triplet and do l++ and r--.
    5. If sum is less than zero then l++
    6. If sum is greater than zero then r--
    

    code:

    void findTriplets(int arr[], int n){
    
        sort(arr, arr+n);
     
        for (int i=0; i<n-1; i++) {
            int l = i + 1;
            int r = n - 1;
            int x = arr[i];
            while (l < r){
                if (x + arr[l] + arr[r] == 0){
                   cout<<x<<" "<<arr[l]<<" "<<arr[r]<<endl;
                    l++;
                    r--;
                }
     
                // If sum of three elements is less
                // than zero then increment in left
                else if (x + arr[l] + arr[r] < 0)
                    l++;
     
                // if sum is greater than zero than
                // decrement in right side
                else
                    r--;
            }
        }
    }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.