4Sum II binary search solution, could anybody optimize it?


  • 0
    public class Solution {
        class MyPair {
            int a;
            int b;
            MyPair(int val1, int val2) {
                this.a = val1;
                this.b = val2;
            }
        }
        public int fourSumCount(int[] A, int[] B, int[] C, int[] D) {
            List<Integer> listAB = new ArrayList<>();
            for (int i = 0; i < A.length; i++)
                for (int j = 0; j < B.length; j++)
                    listAB.add(A[i] + B[j]);
    
            List<Integer> listCD = new ArrayList<>();
            for (int i = 0; i < C.length; i++)
                for (int j = 0; j < D.length; j++)
                    listCD.add(C[i] + D[j]);
    
            if (listAB.size() == 0 || listCD.size() == 0)
                return 0;
            Collections.sort(listAB);
            Collections.sort(listCD);
    
            ArrayList<MyPair> listABPair = new ArrayList<>();
            ArrayList<MyPair> listCDPair = new ArrayList<>();
    
            removeDuplidate(listAB, listABPair);
            removeDuplidate(listCD, listCDPair);
            
            int ans = 0;
            for(int i = 0; i < listCDPair.size(); i++){
                int index = binarySearch(listABPair, -listCDPair.get(i).a);
                if(index != -1){
                    ans += listABPair.get(index).b * listCDPair.get(i).b;
                }
            }
            return ans;
        }
        
        private void removeDuplidate(List<Integer> list, List<MyPair> resultlist){
            int t = list.get(0);
            int count = 1;
            for (int i = 1; i < list.size(); i++) {
                if (list.get(i) == t)
                    count++;
                else {
                    resultlist.add(new MyPair(t, count));
                    t = list.get(i);
                    count = 1;
                }
            }
            resultlist.add(new MyPair(t, count));
        }
        
        private int binarySearch(List<MyPair> list, int target){
            int start = 0;
            int end = list.size()-1;
            while(start <= end){
                int middle = start + (end-start) / 2;
                int compareVal = list.get(middle).a;
                if(compareVal < target){
                    start = middle + 1;
                }else if(compareVal > target){
                    end = middle - 1;
                }else{
                    return middle;
                }
            }
            return -1;
        }
    
    }
    

Log in to reply
 

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