Why my code could run on Eclipse with the time exceed example


  • 0
    S

    public class ThreeSum {
    public static void main(String[] args) {
    int[] num ={7,-1,14,-12,-8,7,2,-15,8,8,-8,-14,-4,-5,7,9,11,-4,-15,-6,1,-14,4,3,10,-5,2,1,6,11,2,-2,-5,-7,-6,2,-15,11,-6,8,-4,2,1,-1,4,-6,-15,1,5,-15,10,14,9,-8,-6,4,-6,11,12,-15,7,-1,-9,9,-1,0,-4,-1,-12,-2,14,-9,7,0,-3,-4,1,-2,12,14,-10,0,5,14,-1,14,3,8,10,-8,8,-5,-2,6,-11,12,13,-7,-12,8,6,-13,14,-2,-5,-11,1,3,-6};

        threeSum(num);
    }
    public static List<List<Integer>> threeSum(int[] num) {
        List<Integer> ListNum=new ArrayList<Integer>();
        for(int i=0;i<num.length;i++){
            ListNum.add(num[i]);
        }
        ListNum.sort(Comparator.naturalOrder());
        List<List<Integer>> Total = new ArrayList<List<Integer>>();
    
        List<Integer> rowlistpre= new ArrayList<>();
    
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    
        for (int i = 0; i < num.length; i++) {
            map.put(ListNum.get(i), i);
    
        }
        for (int i = 0; i < ListNum.size() - 2; i++) {
            for (int j = i + 1; j < ListNum.size() - 1; j++) {
                int value = -ListNum.get(i) - ListNum.get(j);
    
                if (map.containsKey(value) && (map.get(value) >i) && (map.get(value) >j)) {
                    rowlistpre.clear();
                    List<Integer> rowlistnew = new ArrayList<>();
                    rowlistpre.add(ListNum.get(i));
                    rowlistpre.add(ListNum.get(j));
                    rowlistpre.add(value);
                    rowlistnew.addAll(rowlistpre);
                    if(!Total.contains(rowlistnew)) {
                        Total.add(rowlistnew);
                    }
    
                }
            }
        }
        System.out.println("total is"+Total);
        return Total;
    }
    

    }

    I see on the discuss that there is O(N^2) codes being accepted


  • 0
    L

    Hi! sunshinexiazhi, I think you have computed many repeated triplets, you should check your index j and index i,for more details, Please click the URL:http://www.cnblogs.com/lasclocker/p/4417758.html


Log in to reply
 

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