-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathSolution.cs
More file actions
39 lines (36 loc) · 1.25 KB
/
Solution.cs
File metadata and controls
39 lines (36 loc) · 1.25 KB
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
37
38
39
public class Solution
{
public IList<IList<int>> FourSum(int[] nums, int target)
{
IList<IList<int>> ans = [];
Dictionary<long, HashSet<(int a, int b)>> map = [];
HashSet<string> keys = [];
int n = nums.Length;
if (n < 4) return [];
// nums[a] + nums[b] + nums[c] + nums[d] = target
// if a < b < c < d
// nums[a] + nums[b] = target - (nums[c] + nums[d])
map[0L + nums[0] + nums[1]] = [(nums[0], nums[1])];
for (int c = 2; c < n - 1; c++)
{
for (int d = c + 1; d < n; d++)
{
long key = target - (0L + nums[c] + nums[d]);
foreach (var pair in map.GetValueOrDefault(key, []))
{
int[] tmp = [pair.a, pair.b, nums[c], nums[d]];
Array.Sort(tmp);
string ans_key = string.Join("_", tmp);
if (keys.Add(ans_key)) ans.Add(tmp);
}
}
for (int a = c - 1, b = c; a >= 0; a--)
{
long key = 0L + nums[a] + nums[b];
if (!map.ContainsKey(key)) map[key] = [];
map[key].Add((nums[a], nums[b]));
}
}
return ans;
}
}