Leetcode: 3Sum

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

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

Solution:

Time-complexity $O(n^2)$ and space-complexity$O(n)$ (Using HashTable):

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
        for(int i=0; i<num.length; i++)
        {
            if (map.containsKey(num[i]))
                map.put(num[i], map.get(num[i])+1);
            else
                map.put(num[i], 1);
        }
        
        ArrayList<ArrayList<Integer>> sol = new ArrayList<ArrayList<Integer>>();
        for(int i=0; i<num.length-2; i+=map.get(num[i]))
        {
            for(int j=i+1; j<num.length-1; j= num[i]==num[j]? j+map.get(num[j])-1: j+map.get(num[j]))
            {
                int temp= -(num[i]+num[j]);
                int duplicates = temp==num[j] ? temp==num[i] ? 2 : 1 : 0;
                if(temp>= num[j] && map.containsKey(temp) && map.get(temp)>duplicates)
                {
                    ArrayList<Integer> onesol = new ArrayList<Integer> ();
                    onesol.add(num[i]); onesol.add(num[j]); onesol.add(temp); 
                    sol.add(onesol);
                }
            }
        }
        return sol;
    }
}

Time-complexity $O(n^2 log n)$ and space-complexity$O(1)$ (Binary Search):

public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] num) {
        ArrayList<ArrayList<Integer>> solution = new ArrayList<ArrayList<Integer>>();
        Arrays.sort(num);
        for(int i=0; i < num.length-2; i++)
        {
            if(i>0 && num[i-1]==num[i])
                continue;
            for(int j=i+1; j < num.length-1; j++)
            {
                if(j>i+1 && num[j-1]==num[j])
                    continue;
                if (binarySearch(num, -(num[i]+num[j]), j+1, num.length-1))
                {
                    ArrayList<Integer> triplet = new ArrayList<Integer>();
                    triplet.add(num[i]);
                    triplet.add(num[j]);
                    triplet.add(-(num[i]+num[j]));
                    solution.add(triplet);
                }
            }
        }
        return solution;
    }
        
    private boolean binarySearch(int[] num, int goal, int start, int end)
    {
        if (start > end)
            return false;
        int midpoint = (start+end)/2;
        if (num[midpoint]==goal)
            return true;
        else if (num[midpoint]<goal)
            return binarySearch(num, goal, midpoint+1, end);
        else
            return binarySearch(num, goal, start, midpoint-1);
    }
}