TLE but it's O(n^2), please help me improve it! Thank you!


  • 0
    Y
    public static List<List<Integer>> threeSum(int[] sum){
            List<List<Integer>> result = new ArrayList<List<Integer>>();
            if (sum.length <3) return result;
    
            HashMap<Integer, Single> singles = new HashMap<Integer, Single>();
    
            for (int i = 0; i< sum.length; i++){
                singles.put(sum[i], new Single(sum[i],i));
            }
    
            ArrayList<Pair> pairs = new ArrayList<Pair>();
    
            for (int i = 0; i<sum.length; i++){
                for (int j = i+1; j<sum.length; j++){
                    pairs.add(new Pair(sum[i], i, sum[j], j));
                }
            }
    
            for (Pair pair: pairs){
                Single single = singles.get(0-pair.getSum());
                if (single != null && pair.compareIndex(single.getIndex())){
                    ArrayList<Integer> triplet = new ArrayList<Integer>();
                    triplet.add(single.getValue());
                    triplet.add(pair.getFirst());
                    triplet.add(pair.getSecond());
                    Collections.sort(triplet);
                    if (!result.contains(triplet)) result.add(triplet);
                }
            }
    
            return result;
        }
    
    }
    
    class Pair {
        int a;
        int aIndex;
        int b;
        int bIndex;
        int sum;
    
        public Pair(int a, int ai, int b, int bi) {
            this.a = a;
            this.aIndex = ai;
            this.b = b;
            this.bIndex = bi;
            this.sum = a+b;
        }
    
        public boolean compareIndex(int index){
            return aIndex!=index && bIndex!=index;
        }
    
        public int getFirst(){
            return a;
        }
    
        public int getFirstIndex(){
            return aIndex;
        }
    
        public int getSecond(){
            return b;
        }
    
        public int getSecondIndex(){
            return bIndex;
        }
    
        public int getSum(){
            return sum;
        }
    }
    
    class Single {
        private int value;
        private int index;
    
        public Single(int v, int i){
            this.value = v;
            this.index = i;
        }
    
        public int getValue(){
            return value;
        }
    
        public int getIndex(){
            return index;
        }

  • 0
    L

    Hello!,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.