My accepted Java Solution using HashSet. The time complexity is O(n^2).


  • 7
    H
    public List<List<Integer>> threeSum(int[] num) {
        Arrays.sort(num);
        List<List<Integer>> list = new ArrayList<List<Integer>>();
        HashSet<List<Integer>> set = new HashSet<List<Integer>>();
        for(int i=0;i<num.length;i++)
        {
            for(int j=i+1,k=num.length-1;j<k;)
            {
                if(num[i]+num[j]+num[k]==0)
                {
                    List<Integer> l= new ArrayList<Integer>();
                    l.add(num[i]);
                    l.add(num[j]);
                    l.add(num[k]);
                    if(set.add(l))
                    list.add(l);
                    j++;
                    k--;
                }
                else if(num[i]+num[j]+num[k]<0)
                j++;
                else
                k--;
            }
        }
        return list;
    }

  • 5
    W

    I copied you code, and it`s Time Limit Exceeded now


  • 0
    L

    I changed the 5th line to "for(int i=0;i<num.length-2 && nums[i]<=0 ;i++)" and the OJ accepted.


  • 0
    I

    This code will not give time limit

    public List<List<Integer>> threeSum(int[] nums) {
    List<List<Integer>> res=new ArrayList<>();
    Arrays.sort(nums);
    List<Integer> list=null;;

        for(int g = 0; g < nums.length-2 && nums[g]<=0 ; g++){
            if(list!=null&&nums[g]==list.get(0))
                continue;
            int k=nums.length-1;
            int j=g+1;
            
            while(j<k){
                int sum=nums[g]+nums[j]+nums[k];
                
                if(sum==0){
                      
                        if(list==null||list.get(0)!=nums[g]||list.get(1)!=nums[j]&&list.get(2)!=nums[k]){
                            list=new ArrayList();
                            list.add(nums[g]);
                            list.add(nums[j]);
                            list.add(nums[k]);
                            res.add(list);
                        }
                       
                       j++;
                       k--;
                }
                else if(sum>0){
                    k--;
                }else{
                    j++;
                }
            }
        }
        return res;
    }
    

  • 0
    Z

    Time Limit Exceeded


Log in to reply
 

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