Given array with integers, return 3 number with sum of zero.

3sum.cpp

// ref: https://en.wikipedia.org/wiki/3SUM

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

// Brute force solution O(n^3) 
bool sum3A(int arr[], int n) {
  for (int i=0 ; i < n ; i++) {
    for (int j=i+1 ; j < n ; 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;
          return true; 
        }
      }
    }
  }
  
  return false;
}

// Using extra space O(n^2)
bool sum3B(int arr[], int n) {
  map<int,int> hash;
  
  for (int i=0 ; i < n ; i++) {
    hash[arr[i]] = i;
  }
  
  for (int i=0 ; i < n ; i++) {
    for (int j=i+1 ; j < n ; j++) {
      int sum = -1 * (arr[i] + arr[j]);
      if (hash.count(sum) > 0) { //exist
          cout << "a[" << i << "]=" << arr[i] << " arr[" << j << "]=" << arr[j] << " arr[" << hash[sum] << "]=" << "" << sum << endl;
          return true;         
      }  
    }
  }
  
  return false;
}

// Without extra space~ O(n^2)
bool sum3C(int arr[], int n) {
  sort(arr,arr+n);
  
  for (int i=0 ; i < n ; i++) {
    
    int start = i+1;
    int end = n-1;

    while (start < end) {
      int sum = -(arr[start] + arr[end]);
      if (arr[i] == sum) {
        cout << "a[" << i << "]=" << arr[i] << " arr[" << start << "]=" << arr[start] << " arr[" << end << "]=" << "" << arr[end] << endl;
        return true;
      }
      
      if (sum < arr[i])
        end--;
      else
        start++;
    }
  }
  
  return false;
}

int main() {
  int arr[] =   {1,-3,2,7,-7, 0}; 
  
  sum3C(arr,sizeof(arr)/sizeof(int));

  return 0;
}