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

• ``````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++)

List<Integer> listCD = new ArrayList<>();
for (int i = 0; i < C.length; i++)
for (int j = 0; j < D.length; 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 {
t = list.get(i);
count = 1;
}
}
}

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;
}

}
``````

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