3Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Notice that the solution set must not contain duplicate triplets.

Example 1:

Input: nums = {-1,0,1,2,-1,-4}
Output: [[-1,-1,2],[-1,0,1]]

Approach

Java

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
public class ThreeSum {
    public static void main(String[] args) {
        int nums[] = { -1, 0, 1, 2, -1, -4 };
        List<List<Integer>> sum = threeSum(nums);
        System.out.println(Arrays.asList(sum));
    }
    static List<List<Integer>> threeSum(int[] nums) {
        int n = nums.length;
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if (n < 3)
            return res;
        // sort the array
        Arrays.sort(nums);
        for (int i = 0; i < n - 2; i++) {
            int low = i + 1;
            int high = n - 1;
            if (i > 0 && nums[i] == nums[i - 1])
                continue;
            while (low < high) {
                if (nums[low] + nums[high] + nums[i] == 0) {
                    List<Integer> x = new ArrayList<Integer>();
                    x.add(nums[i]);
                    x.add(nums[low]);
                    x.add(nums[high]);
                    res.add(x);
                    low++;
                    high--;
                    while (low < high && nums[high] == nums[high + 1])
                        high--;
                    while (low < high && nums[low] == nums[low - 1])
                        low++;
                } else if (nums[low] + nums[high] + nums[i] > 0)
                    high--;
                else
                    low++;
            }
        }
        return res;
    }
}

C++

#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) 
{
        int n=nums.size();
        vector<vector<int>> res;
        if(n<3)
               return res;
        sort(nums.begin(),nums.end());
        for(int i=0;i<n-2;i++)
        {
            int low=i+1;
           int  high=n-1;
            if(i>0 && nums[i]==nums[i-1])
                   continue;
            while(low<high)
            {
         if(nums[low]+nums[high]+nums[i]==0)
               {
                   vector<int> x;
                   x.push_back(nums[i]);
                   x.push_back(nums[low]);
                   x.push_back(nums[high]);
                   res.push_back(x);
                   low++;
                   high--;
                   while(low<high &&nums[high]==nums[high+1])
                          high--;
                   while(low<high && nums[low]==nums[low-1])
                          low++;
               }
             else if(nums[low]+nums[high]+nums[i]>0)
                     high--;
             else
                 low++;
            }
        }
        return res;
}
int main()
{
   vector<int> nums ={-1,0,1,2,-1,-4};
   vector<vector<int>> sum=threeSum(nums);
   cout<<"[";
   for(int i=0;i<sum.size();i++)
     {
         cout<<"[";
         for(int j=0;j<sum[i].size();j++)
          {
              cout<<sum[i][j];
              if(j!=sum[i].size()-1)
                 cout<<",";
                
          }
        if(i!=sum.size()-1)
           cout<<"],";
        else
         cout<<"]";
        
     }
    cout<<"]";
  return 0;
    
}