# 3 different ways of solving 3sum

• 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--;
}
}
}
``````

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