Get Time out for O(n^2) method


  • 0
    Z

    Any suggestion for my code, I think it only loop twice. So it should be O(n^2)

      public class Solution {
    public List<List<Integer>> threeSum(int[] num) {
      //  record the result
      List<List<Integer>> allSumlist=new ArrayList<List<Integer>>();
      if (num.length<3) {return allSumlist;}
     // hashmap to record all element with index for this element in the array num
      HashMap<Integer, ArrayList<Integer>> numSet=new HashMap<Integer, ArrayList<Integer>>();
     // record all elements into this hashMap      
       for (int i=0; i<num.length; i++) {
          if (numSet.containsKey(num[i])) { numSet.get(num[i]).add(i);}
           else { 
               ArrayList<Integer> newIndex=new ArrayList<Integer>();
                newIndex.add(i);
                numSet.put(num[i], newIndex);
             }
          }
        
      //  double loop, check the third one using hashmap, if the index of this element is greater than j, we get a solution and add it to our result  
         for (int i=0; i<num.length-2; i++) {
           for (int j=i+1; j<num.length-1; j++) {
              int k= 0-num[i]-num[j];
              if (numSet.containsKey(k)) { 
                for (int x : numSet.get(k) ) {
       //  if the third element index is greater than j, then we find a solution
                   if (x>j) { 
                       ArrayList<Integer> newSumSet=new ArrayList<Integer>();
                       newSumSet.add(num[i]);
                       newSumSet.add(num[j]);
                       newSumSet.add(k);
                       allSumlist.add(newSumSet);
                          }    
                     }   
                  
               }
          }
          
      }       
          
          
     return allSumlist;    
        
    }
    

    }


  • 0
    M

    I have similar code with you and also got time limit problem. The reason I think is that this code could have a worst case complexity of O(n^3) when there are a lot of array elements with the same value.


Log in to reply
 

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