# One hash map and one double loop

• It is O(n^3) time complexity and O(n^2) space complexity. But besides adding the 4sums to the list, the search part is O(n^2) time-complexity. So in case we have less than O(n^2) lists of 4 sums it is O(n^2).

``````public class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
List<List<Integer>> ans = new ArrayList<List<Integer>>();
if (nums.length < 4) return ans;
Arrays.sort(nums);
// boundary case
if (target % 4==0) {
int a = target/4;
for (int l = 0; l < nums.length; l++) {
if (nums[l] == a && l+3 < nums.length && nums[l] == nums[l+3]){
break;
}
}
}
Map<Integer, ArrayList<Integer>> twoSumMap = new HashMap<>();
int i = 0;
// We traverse all pairs (i, j) for i < j and (nums[i], nums[j]) distinct.
// Check if (nums[i], nums[j]) can be the third and fourth number in the 4 sum. If so, add them
// Put (nums[i], nums[j]) in a Hashmap that stores all possible first and second number in the 4 sum.
// In order to keep as much information as possible, we use nums[i] + nums[j] as the key in the hashmap
// and the first index i for nums[i] as the value.
// It has the property that if x = nums[map.get(sum)] and y = sum - x, then x <= y
// and the pair (x, y) is not repeated

while (i < nums.length) {
int j = i+1;
while (j < nums.length) {
int sum = nums[i] + nums[j];
if (2*sum > target && twoSumMap.containsKey(target - sum)) {
add(i, j, target, nums, twoSumMap, ans);
}
if (twoSumMap.containsKey(sum)) {
} else {
twoSumMap.put(nums[i] + nums[j], new ArrayList<Integer>(Arrays.asList(i)));
}
j = getLastIndex(j, nums);
j++;
}
i = getLastIndex(i, nums);
i++;
}
return ans;
}
// a1, a2, a3, a4 are the four numbers in the 4sum.
// Check that they are not duplicated before adding them to the list.
// The only possibly duplicated cases are a1 < a2 = a3 < a4. a1 = a2 = a3 < a4 or a1 < a2 = a3 = a4
private void add(int i, int j, int target, int[] nums, Map<Integer, ArrayList<Integer>> map, List<List<Integer>> list) {
int a3 = nums[i], a4 = nums[j], x = target - a3 - a4;
ArrayList<Integer> lx = map.get(x);
for (Integer i1 : lx) {
int a1 = nums[i1], a2 = x - a1;
if (a2 < a3) list.add(new ArrayList<Integer>(Arrays.asList(a1, a2, a3, a4)));
else if (a2 == a3) {
if (a1 == a3 || a2 == a4) {
if (i+2 < nums.length && nums[i] == nums[i+2])
} else if (i+1 < nums.length && nums[i] == nums[i+1])