Sponsored
Sponsored
This approach employs sorting the array and fixing two pointers while searching for the other two via a two-pointer method. This reduces the dimensionality of the problem stepwise.
Time Complexity: O(n^3), where n is the number of elements in the array due to three nested loops.
Space Complexity: O(1), excluding the space required for the output storage.
1import java.util.ArrayList;
2import java.util.Arrays;
3import java.util.List;
4
5public class FourSum {
6 public List<List<Integer>> fourSum(int[] nums, int target) {
7 Arrays.sort(nums);
8 List<List<Integer>> result = new ArrayList<>();
9 int n = nums.length;
10 for (int i = 0; i < n - 3; i++) {
11 if (i > 0 && nums[i] == nums[i - 1]) continue;
12 for (int j = i + 1; j < n - 2; j++) {
13 if (j > i + 1 && nums[j] == nums[j - 1]) continue;
14 int k = j + 1, l = n - 1;
15 while (k < l) {
16 int sum = nums[i] + nums[j] + nums[k] + nums[l];
17 if (sum == target) {
18 result.add(Arrays.asList(nums[i], nums[j], nums[k], nums[l]));
19 while (k < l && nums[k] == nums[k + 1]) k++;
20 while (k < l && nums[l] == nums[l - 1]) l--;
21 k++; l--;
22 } else if (sum < target) {
23 k++;
24 } else {
25 l--;
26 }
27 }
28 }
29 }
30 return result;
31 }
32
33 public static void main(String[] args) {
34 FourSum solver = new FourSum();
35 int[] nums = {1, 0, -1, 0, -2, 2};
36 int target = 0;
37 List<List<Integer>> result = solver.fourSum(nums, target);
38 for (List<Integer> res : result) {
39 System.out.println(res);
40 }
41 }
42}Java's solution utilizes Arrays.sort for quick sorting and ArrayList for dynamic storage of resulting quadruplets. The algorithm detects target-compliant sums while traversing the array with nested loops, preventing duplicate evaluations.
This method reduces the four-sum problem by first reducing it to a three-sum problem, and then a two-sum problem using hash maps.
Time Complexity: O(n^2), considering the use of a hash map.
Space Complexity: O(n), for storing intermediate and potential pairs.
1
This solution uses a hash map to store potential pairs and provides an immediate reference to check against the target. Developing all valid pairs without duplicates requires keeping unique property checks on loop iterations.