# Java solution with n^2 time complexity at best cases

• Main idea: This solution is totally based on 2sum.
First use a hashmap to store the all 2sum values. The key is the sum, and the value is a linkedlist that stores all index (i, j) that can have a sum equal to the key.
Second, add each two elements again as 1st and 2nd and get the new target(target - num[x] - nums[y]). The new target should exist in the hashmap and the all index(i, j) in the the value list could possibly be the 3rd and 4th elements. There are two situation met and then the 3rd and 4th are valid. (1) index[2nd] < index[3rd] (2) nums[index[3rd]] is not in the set. If the value is in this set, it means the 3rd and 4th are duplicated.
Note: in the second step, the 1st and 2nd should also be not duplicated. The way to solve it is very similar in 2sum.

`````` public List<List<Integer>> fourSum(int[] nums, int target) {
Arrays.sort(nums);
for (int i = 0; i < nums.length - 1; i++) {
for (int j = i + 1; j < nums.length; j++) {
if (!map.containsKey(nums[i] + nums[j])) {
map.put(nums[i] + nums[j], list);
} else {
}
}
}
for (int i = 0; i < nums.length - 1; i++) {
if (i != 0 && nums[i] == nums[i - 1]) {
continue;
}
for (int j = i + 1; j < nums.length; j++) {
if (j != i + 1 && nums[j] == nums[j - 1]) {
continue;
}
int newTarget = target - nums[i] - nums[j];
//Used to record the unique third element
Set<Integer> set = new HashSet<Integer>();
if (map.containsKey(newTarget)) {
for (int[] index: map.get(newTarget)) {
//third and fourth should be on the right side
if (j < index[0] && !set.contains(nums[index[0]])) {