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.
1using System;
2using System.Collections.Generic;
3
4class FourSumSolution {
5 public IList<IList<int>> FourSum(int[] nums, int target) {
6 Array.Sort(nums);
7 List<IList<int>> result = new List<IList<int>>();
8 int n = nums.Length;
9 for (int i = 0; i < n - 3; i++) {
10 if (i > 0 && nums[i] == nums[i - 1]) continue;
11 for (int j = i + 1; j < n - 2; j++) {
12 if (j > i + 1 && nums[j] == nums[j - 1]) continue;
13 int k = j + 1, l = n - 1;
14 while (k < l) {
15 int sum = nums[i] + nums[j] + nums[k] + nums[l];
16 if (sum == target) {
17 result.Add(new List<int>{nums[i], nums[j], nums[k], nums[l]});
18 while (k < l && nums[k] == nums[k + 1]) k++;
19 while (k < l && nums[l] == nums[l - 1]) l--;
20 k++; l--;
21 } else if (sum < target) {
22 k++;
23 } else {
24 l--;
25 }
26 }
27 }
28 }
29 return result;
30 }
31
32 static void Main() {
33 var solver = new FourSumSolution();
34 int[] nums = {1, 0, -1, 0, -2, 2};
35 int target = 0;
36 var result = solver.FourSum(nums, target);
37 foreach (var r in result) {
38 Console.WriteLine("[{0}]", string.Join(", ", r));
39 }
40 }
41}This C# solution employs Array sorting and List-based storage for finding and storing quadruplets. The sorted array allows the closing pair to change dynamically, maintaining the requirement of forming the target sum without duplicates.
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.