Accepted by OJ, but too slow(764ms), any improvement?


  • 0
    D

    The idea is to build the pairs twice. At first the hashmap for (ab) is built from left to right, and it record indices for the first appearing pair, ignoring duplicated pairs that follow the recorded pair. Then I build another hashmap for (cd) from right to left, still ignoring duplicated pairs. Then we could iterate through the two hash maps and merge pairs that satisfy the conditions for 4-sum and the order requirement that the indices for b must proceed that for c.

    hash_ab records only once the same pairs of numbers that are constructed from leftmost possible indices and hash_cd is recorded from rightmost possible indices, and all the duplicates in between are discarded. I guess it could be a trouble of time efficiency.

    public class Solution {
        private static class Pair { 
            int left; 
            int right; 
            public Pair(int l, int r) { 
                left = l; 
                right = r; 
            } 
        } 
        public static List<List<Integer>> fourSum(int[] num, int target) { 
            Arrays.sort(num); 
            List<List<Integer>> result = new ArrayList<List<Integer>>(); 
             
            //Build two hashmaps that are generated from iterating from left and right, respectively. Ignoring all the duplicated 
            // pairs while retaining only the first encountered nonduplicating pair during the process 
            HashMap<Integer, List<Pair>> hash_ab = new HashMap<Integer, List<Pair>>();//used for picking (a,b) 
            HashMap<Integer, List<Pair>> hash_cd = new HashMap<Integer, List<Pair>>();//used for picking (c,d) 
            int len = num.length; 
            for(int i = 0; i < len; i++){ 
                if(i > 0 && num[i-1] == num[i]) continue; 
                for(int j = i + 1; j < len; j++) { 
                    if(j > i + 1 && num[j-1] == num[j]) continue; 
                    int k = num[i] + num[j]; 
                    Pair pair = new Pair(i,j);
                    if(hash_ab.containsKey(k)) hash_ab.get(k).add(pair);
                    else {
                        List<Pair> pairs = new ArrayList<Pair>();
                        pairs.add(pair);
                        hash_ab.put(k, pairs); 
                    }
                } 
            } 
            for(int i = len - 1; i > -1; i--){ 
                if(i < len - 1 && num[i+1] == num[i]) continue; 
                for(int j = i - 1; j > -1; j--) { 
                    if(j < i - 1 && num[j+1] == num[j]) continue; 
                    int k = num[i] + num[j]; 
                    Pair pair = new Pair(j,i);
                    if(hash_cd.containsKey(k)) hash_cd.get(k).add(pair);  
                    else {
                        List<Pair> pairs = new ArrayList<Pair>();
                        pairs.add(pair);
                        hash_cd.put(k, pairs); }
                } 
            } 
    
            for(Integer i: hash_ab.keySet()) { 
                for(Pair ab: hash_ab.get(i)) {
                    if(!hash_cd.containsKey(target - i)) continue;
                    for(Pair cd: hash_cd.get(target - i)){ 
                        if(ab.right < cd.left) {           
                            List<Integer> abcd = new ArrayList<Integer>(); 
                            abcd.add(num[ab.left]); abcd.add(num[ab.right]);  
                            abcd.add(num[cd.left]); abcd.add(num[cd.right]); 
                            result.add(abcd); 
                        } 
                    } 
                }
            } 
            return result; 
        } 
    }

  • 0
    F
    This post is deleted!

Log in to reply
 

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