Java O(n^2*logn) solution but runs too slowly,how to optimize it


  • 0
    B
    public class Solution {
    private List<List<Integer>> result=new ArrayList<List<Integer>>();
    private HashMap<Integer,ArrayList<Twins>> twoSum;
    private int target;
    private int length;
    
    public List<List<Integer>> fourSum(int[] nums, int target) {
        if(nums==null||nums.length<4){
            return new ArrayList<List<Integer>>(); 
        }
        Arrays.sort(nums);
        this.init(nums,target);
        int cacheI=nums[0]-1;
        int cacheJ=nums[0]-1;
    li: for(int i=0;i<this.length;i++){
            cacheJ=nums[0]-1;
            if(nums[i]==cacheI){
                continue li;
            }
            else{
                cacheI=nums[i];
    lj:         for(int j=i+1;j<this.length;j++){
                    if(nums[j]==cacheJ){
                        continue lj;
                    }else{
                        cacheJ=nums[j];
                        int k=target-nums[i]-nums[j];
                        if(twoSum.containsKey(k)){
                            ArrayList<Twins> twinsList=twoSum.get(k);
                            for(int m=0;m<twinsList.size();m++){
                                Twins t=twinsList.get(m);
                                if(t.getX()>j){//make sure they are non-descending
                                    ArrayList<Integer> temp=new ArrayList<Integer>();
                                    temp.add(nums[i]);
                                    temp.add(nums[j]);
                                    temp.add(nums[t.getX()]);
                                    temp.add(nums[t.getY()]);
                                    this.result.add(temp);
                                }
                            }
                        }
                    }
                }
            }
    
        }
        return this.result;
    }
    
    private void init(int[] nums,int target){
        this.target=target;
        this.length=nums.length;
        this.twoSum=new HashMap<Integer,ArrayList<Twins>>();
        for(int i=0;i<nums.length;i++){
            for(int j=i+1;j<nums.length;j++){
                int sum=nums[i]+nums[j];
                if(this.twoSum.containsKey(sum)){
                    ArrayList<Twins> list=this.twoSum.get(sum);
                    Twins last=list.get(list.size()-1);
                    if(nums[j]==nums[last.getY()]){
                        this.twoSum.get(sum).remove(list.size()-1);
                    }
                    this.twoSum.get(sum).add(new Twins(i,j));
                }else{
                    ArrayList temp=new ArrayList();
                    temp.add(new Twins(i,j));
                    this.twoSum.put(sum,temp);
                }
            }
        }
    }
    
    private class Twins{
        public int x;
        public int y;
        
        public Twins(int ix,int iy){
            x=ix;
            y=iy;
        }
        public int getX(){
            return x;
        }
        public int getY(){
            return y;
        }
        
        public boolean equals(Object o){
            if(o instanceof Twins){
                Twins t=(Twins)o;
                if(this.x==t.x||this.y==t.y){
                    return true;
                }
            }
            return false;
        }
        
        public int HashCode(){
            int result=17;
            result=31*result+this.x;
            result=31*result+this.y;
            return result;
        }
    }
    

    }


Log in to reply
 

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