Simple Solution O(n^2) with explanation


  • 0
    S

    '''
    public List<List<Integer>> threeSum(int[] nums) {

        //this method works for unique triplets and is much more efficient 
        List<Integer> set = new ArrayList<>();
        //hashset to consider only unique triplets
        Set<String> sample = new HashSet<>();
        //list of lists
        List<List<Integer>> result = new ArrayList<>();
        int l;
        int r;
        //sorting the array
        Arrays.sort(nums);
        if(nums.length<3)
        {
            //if less than length 3, then we cannot form triplet
            return result;
        }
        else if((nums[0] == nums[nums.length-1]) && (nums[0]==0))
        {
            //if all the elements are same and zero 
            set.add(0);
            set.add(0);
            set.add(0);
            result.add(set);
            return result;
        }
        else if(nums[0] == nums[nums.length-1])
        {
            //if all the elements are same and non zero
            //it is not possible to form a triplet if the value is not zero
            return result;
        }
        else
        {
            //for all other cases
            for (int i = 0; i < nums.length - 2; i++) 
                {
                    // To find the other two elements, start two index variables
                    // from two corners of the array and move them toward each
                    // other
                    l = i + 1; // index of the first element in the remaining elements
                    r = nums.length - 1; // index of the last element
                    while (l < r) 
                    {
                        if (nums[i] + nums[l] + nums[r] == 0) 
                        {
                           //if we dont break, then we go into infinte loop as always this condition gets satisfied in the next                                iteration
                            String s = Integer.toString(nums[i]) + Integer.toString(nums[l]) + Integer.toString(nums[r]);
                            if(!sample.contains(s))
                            {
                                 //then only add it to the result list
                                set.add(nums[i]);
                                set.add(nums[l]);
                                set.add(nums[r]);
                                result.add(set);
                                sample.add(s);
                                set = new ArrayList();
                            }
                            //here we do l++ or r-- just to go to the next triplet
                            // if the question is just return true, if we find a triplet with the sum, then break statement                                    // should suffice
                            r--;
                        }
                        else if (nums[i] + nums[l] + nums[r] < 0)
                        {
                            l++;
                        }
                        else 
                        {
                            // nums[i] + nums[l] + nums[r] > 0
                            r--;
                        }
    
                    }
                }
            
        }//end of else
    return result;
       
    }
    

    '''


Log in to reply
 

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