
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.
1function fourSum(nums, target) {
2 nums.sort((a, b) => a - b);
3 const results = [];
4 const n = nums.length;
5 for (let i = 0; i < n - 3; i++) {
6 if (i > 0 && nums[i] === nums[i - 1]) continue;
7 for (let j = i + 1; j < n - 2; j++) {
8 if (j > i + 1 && nums[j] === nums[j - 1]) continue;
9 let k = j + 1, l = n - 1;
10 while (k < l) {
11 const sum = nums[i] + nums[j] + nums[k] + nums[l];
12 if (sum === target) {
13 results.push([nums[i], nums[j], nums[k], nums[l]]);
14 while (k < l && nums[k] === nums[k + 1]) k++;
15 while (k < l && nums[l] === nums[l - 1]) l--;
16 k++; l--;
17 } else if (sum < target) {
18 k++;
19 } else {
20 l--;
21 }
22 }
23 }
24 }
25 return results;
26}
27
28// Example Usage
29const nums = [1, 0, -1, 0, -2, 2];
30const target = 0;
31console.log(fourSum(nums, target));JavaScript handles the solution efficiently through in-built sorting and Array methods. The two-pointer framework after sorting allows an effective traversal for the problem's solution, avoiding excessive identical checks with conditions.
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.
1using System.Collections.Generic;
class FourSumSolution {
public IList<IList<int>> FourSum(int[] nums, int target) {
Array.Sort(nums);
List<IList<int>> result = new List<IList<int>>();
int n = nums.Length;
for (int i = 0; i < n - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
HashSet<int> seen = new HashSet<int>();
for (int k = j + 1; k < n; k++) {
int complement = target - nums[i] - nums[j] - nums[k];
if (seen.Contains(complement)) {
result.Add(new List<int>{nums[i], nums[j], nums[k], complement});
while (k + 1 < n && nums[k] == nums[k + 1]) k++;
}
seen.Add(nums[k]);
}
}
}
return result;
}
static void Main() {
var solver = new FourSumSolution();
int[] nums = {1, 0, -1, 0, -2, 2};
int target = 0;
var result = solver.FourSum(nums, target);
foreach (var r in result) {
Console.WriteLine("[{0}]", string.Join(", ", r));
}
}
}In C#, through increased computational capacities with hash sets, overlaps are checked against reference maps. Sorting allows structured evaluation and quick lookups via the hash tables.