Reference: LeetCode
Difficulty: Medium

My Post: Similar to 3Sum, Use Two Pointers [Java] Easy-Understand

Problem

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

Example: 

1
2
3
4
5
6
7
8
9
10
11
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

Input: [0, 0, 0, 0], and target = 0.
Output: [[0, 0, 0, 0]]

Analysis

3Sum + 4Sum

Use two pointers in 3Sum.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
public List<List<Integer>> fourSum(int[] nums, int target) {
  int n = nums.length;
  // sorting
  Arrays.sort(nums);
  // fourSum
  List<List<Integer>> result = new ArrayList<>();
  for (int i = 0; i < n; ++i) {
    if (i > 0 && nums[i - 1] == nums[i]) continue;
    threeSum(nums, i + 1, n - 1, target - nums[i], result);
  }
  return result;
}
  
private void threeSum(int[] nums, int lo, int hi, int target, List<List<Integer>> result) {
  int n = nums.length;
  int subLen = hi - lo + 1;
  for (int i = lo; i <= hi; ++i) {
    if (i > lo && nums[i] == nums[i - 1]) continue;  // skip same result
    // two pointers
    int j = i + 1, k = hi;
    int t = target - nums[i];
    while (j < k) { // each element is only used once
      if (nums[j] + nums[k] < t) {
        ++j;
      } else if (nums[j] + nums[k] > t) {
        --k;
      } else { // equal
        result.add(Arrays.asList(nums[lo - 1], nums[i], nums[j], nums[k]));
        ++j;
        --k;
        while (j < k && nums[j] == nums[j - 1]) j++;  // skip same result
        while (j < k && nums[k] == nums[k + 1]) k--;  // skip same result
      }
    }
  }
}

Time: $O(N^3)$
Space: $O(1)$