Java solution with n^2 time complexity at best cases


  • 1
    B

    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);
                LinkedList ll = new LinkedList();
                Map<Integer, LinkedList<int[]>> map = new HashMap<Integer, LinkedList<int[]>>();
                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])) {
                            LinkedList<int[]> list = new LinkedList<int[]>();
                            map.put(nums[i] + nums[j], list);
                            list.add(new int[] {i, j});
                        } else {
                            map.get(nums[i] + nums[j]).add(new int[]{i, j});
                        }
                    }
                }
                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]])) {
                                    LinkedList<Integer> list = new LinkedList<Integer>();
                                    ll.add(list);
                                    list.add(nums[i]);
                                    list.add(nums[j]);
                                    list.add(nums[index[0]]);
                                    list.add(nums[index[1]]);
                                    set.add(nums[index[0]]);
                                }
                            }
                        }
                    }
                }
                return ll;
            }

Log in to reply
 

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