Approach 1:
Let the input array be A[].

Create an auxiliary array aux[] and store sum of all possible pairs in aux[]. The size of aux[] should be
n(n1)/2* where n is the size of A[]. Time complexity is O(n^2)

Sort the auxiliary array aux[]. Time complexity is O(n^2logn) for sorting the array of size n^2

Now the problem reduces to find two elements in aux[] with sum equal to X.
The worst case time complexity of the algorithm is O(n^2logn) due to sorting operation of the auxiliary array.
Approach 2:
Here is another approach given by zhaohaoshu

A TreeMap<Integer, List> to store pairs of numbers that can be used to get the number.

Then iterate the map. When two lists of pairs that can get the target are found, cross join the pairs
Map has N^2 keys. The n^2log(n) part is for doing insertion into the tree map. The time complexity to build the map is considered, as it is the deciding factor to consider the running time asymptotically which is O(n^2logn).
NOTE: Above optimizations from O(n^3) time complexity are possible at the cost of auxiliary space of O(n^2) allocated for map.
import java.util.TreeMap;
public class Solution {
class Pair {
int a;
int ai;
int b;
int bi;
public Pair(int a, int ai, int b, int bi){
this.a = a;
this.ai = ai;
this.b = b;
this.bi = bi;
}
boolean same(Pair p){
return p != null && p.a == a && p.b == b;
}
}
public List<List<Integer>> fourSum(int[] num, int target) {
List<List<Integer>> res = new ArrayList<>();
if(num.length < 4){
return res;
}
Arrays.sort(num);
TreeMap<Integer, List<Pair>> map = new TreeMap<>();
for(int i = 0; i < num.length; i++){
for(int j = i + 1; j < num.length; j++){
Pair pair = new Pair(num[i], i, num[j], j);
int sum = num[i] + num[j];
List<Pair> list;
if(map.containsKey(sum)){
list = map.get(sum);
}
else{
list = new ArrayList<>();
map.put(sum, list);
}
list.add(pair);
}
}
Integer first = map.firstKey();
Integer last = map.lastKey();
while(first != null && last != null && first <= last){
if(first + last > target){
last = map.lowerKey(last);
}
else if(first + last < target){
first = map.higherKey(first);
}
else if(first == last){
List<Pair> list = map.get(first);
for(int i = 0; i < list.size(); i++){
Pair a = list.get(i);
if(a.a == a.b){
for(int j = i + 1; j < list.size(); j++){
Pair b = list.get(j);
if(b.a == b.b){
if(a.bi < b.ai){
res.add(Arrays.asList(new Integer[]{a.a, a.b, b.a, b.b}));
break;
}
}
else{
break;
}
}
break;
}
}
last = map.lowerKey(last);
first = map.higherKey(first);
}
else{
Pair lastA = null;
for(Pair a : map.get(first)){
if(a.same(lastA)){
continue;
}
lastA = a;
Pair lastB = null;
for(Pair b: map.get(last)){
if(a.bi < b.ai){
if(b.same(lastB)){
continue;
}
lastB = b;
res.add(Arrays.asList(new Integer[]{a.a, a.b, b.a, b.b}));
}
}
}
last = map.lowerKey(last);
first = map.higherKey(first);
}
}
return res;
}
}