# Same logic as 2sum but use all pairs, O(N^3), using hash map + set

• ``````public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
Set<Set<Integer>> resH = new HashSet<>();
List<List<Integer>> res = new ArrayList<>();
Map<Integer, List<int[]>> pairs = new HashMap<>();

for(int i=0; i<nums.length; i++){
for(int j=i+1; j<nums.length; j++){
int sum = nums[i] + nums[j];
List<int[]> x;
if(pairs.containsKey(target - sum)){
x = pairs.get(target - sum);
}else{
x = new ArrayList<>();
}
pairs.put(target - sum, x);
}
}

for(int i=0; i<nums.length; i++){
for(int j=i+1; j<nums.length; j++){
int sum = nums[i] + nums[j];
if(pairs.containsKey(sum)){
for(int[] firstTwo : pairs.get(sum)){
int[] quadIdx = new int[]{i, j, firstTwo[0], firstTwo[1]};

boolean exit = false;
for(int k=0; k<4; k++){
for(int w=k+1; w<4; w++){
exit = true;
break;
}
}
if(exit) break;
}
if(exit) continue;

}

}
}
}
}
return res;
}
}``````

• I am not positive to call this O(N^3) if anybody thinks this is wrong or has a tighter analysis please let me know thanks

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