18. 4Sum
leetcode medium
Task
Учитывая массив nums из n целых чисел, верните массив всех уникальных четверок [nums[a], nums[b], nums[c], nums[d]] таких, что:0 <= a, b, c, d < n
a, b, c и d различны.
nums[a] + nums[b] + nums[c] + nums[d] == цель
Вы можете вернуть ответ в любом порядке.
C# solution
matched/originalpublic class Solution {
public IList<IList<int>> FourSum(int[] nums, int target) {
var rs = new List<IList<int>>();
Array.Sort(nums);
Helper(rs, nums, target, 4, 0, new List<int>());
return rs;
}
private void Helper(List<IList<int>> rs, int[] nums, long target, int k, int index, List<int> subList) {
if (k == 2) {
int l = index;
int r = nums.Length - 1;
while (l < r) {
long sum = nums[l] + nums[r];
if (sum == target) {
subList.Add(nums[l]);
subList.Add(nums[r]);
rs.Add(new List<int>(subList));
subList.RemoveAt(subList.Count - 1);
subList.RemoveAt(subList.Count - 1);
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r - 1] == nums[r]) {
r--;
}
l++;
r--;
} else if (sum < target) {
l++;
} else {
r--;
}
}
} else {
for (int i = index; i < nums.Length - k + 1; i++) {
if (i != index && nums[i] == nums[i - 1]) {
continue;
}
subList.Add(nums[i]);
Helper(rs, nums, target - nums[i], k - 1, i + 1, subList);
subList.RemoveAt(subList.Count - 1);
}
}
}
}C++ solution
auto-draft, review before submit#include <bits/stdc++.h>
using namespace std;
// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
public IList<vector<int>> FourSum(vector<int>& nums, int target) {
var rs = new List<vector<int>>();
sort(nums.begin(), nums.end());
Helper(rs, nums, target, 4, 0, new List<int>());
return rs;
}
private void Helper(List<vector<int>> rs, vector<int>& nums, long target, int k, int index, List<int> subList) {
if (k == 2) {
int l = index;
int r = nums.size() - 1;
while (l < r) {
long sum = nums[l] + nums[r];
if (sum == target) {
subList.push_back(nums[l]);
subList.push_back(nums[r]);
rs.push_back(new List<int>(subList));
subList.RemoveAt(subList.size() - 1);
subList.RemoveAt(subList.size() - 1);
while (l < r && nums[l] == nums[l + 1]) {
l++;
}
while (l < r && nums[r - 1] == nums[r]) {
r--;
}
l++;
r--;
} else if (sum < target) {
l++;
} else {
r--;
}
}
} else {
for (int i = index; i < nums.size() - k + 1; i++) {
if (i != index && nums[i] == nums[i - 1]) {
continue;
}
subList.push_back(nums[i]);
Helper(rs, nums, target - nums[i], k - 1, i + 1, subList);
subList.RemoveAt(subList.size() - 1);
}
}
}
}Java solution
matched/originalpublic class Solution {
int len = 0;
public List<List<Integer>> fourSum(int[] nums, int target) {
len = nums.length;
Arrays.sort(nums);
return kSum(nums, target, 4, 0);
}
private ArrayList<List<Integer>> kSum(int[] nums, int target, int k, int index) {
ArrayList<List<Integer>> res = new ArrayList<>();
if (index >= len) {
return res;
}
if (k == 2) {
int i = index, j = len - 1;
while (i < j) {
// Find a pair
if (target - nums[i] == nums[j]) {
List<Integer> temp = new ArrayList<>();
temp.add(nums[i]);
temp.add(target - nums[i]);
res.add(temp);
// Skip duplicates
while (i < j && nums[i] == nums[i + 1]) i++;
while (i < j && nums[j - 1] == nums[j]) j--;
i++;
j--;
} else if (target - nums[i] > nums[j]) {
i++;
} else {
j--;
}
}
} else {
for (int i = index; i < len - k + 1; i++) {
// Use current number to reduce kSum into k-1Sum
ArrayList<List<Integer>> temp = kSum(nums, target - nums[i], k - 1, i + 1);
if (temp != null) {
// Add previous results
for (List<Integer> t : temp) {
t.add(0, nums[i]);
}
res.addAll(temp);
}
// Skip duplicates
while (i < len - 1 && nums[i] == nums[i + 1]) {
i++;
}
}
}
return res;
}
}JavaScript solution
matched/original/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function (nums, target) {
const n = nums.length;
const ans = [];
if (n < 4) {
return ans;
}
nums.sort((a, b) => a - b);
for (let i = 0; i < n - 3; ++i) {
if (i > 0 && nums[i] === nums[i - 1]) {
continue;
}
for (let j = i + 1; j < n - 2; ++j) {
if (j > i + 1 && nums[j] === nums[j - 1]) {
continue;
}
let [k, l] = [j + 1, n - 1];
while (k < l) {
const x = nums[i] + nums[j] + nums[k] + nums[l];
if (x < target) {
++k;
} else if (x > target) {
--l;
} else {
ans.push([nums[i], nums[j], nums[k++], nums[l--]]);
while (k < l && nums[k] === nums[k - 1]) {
++k;
}
while (k < l && nums[l] === nums[l + 1]) {
--l;
}
}
}
}
}
return ans;
};Python solution
matched/originaldef fourSum(self, nums, target):
nums.sort()
results = []
self.findNsum(nums, target, 4, [], results)
return results
def findNsum(self, nums, target, N, result, results):
if len(nums) < N or N < 2: return
# solve 2-sum
if N == 2:
l,r = 0,len(nums)-1
while l < r:
if nums[l] + nums[r] == target:
results.append(result + [nums[l], nums[r]])
l += 1
r -= 1
while l < r and nums[l] == nums[l - 1]:
l += 1
while r > l and nums[r] == nums[r + 1]:
r -= 1
elif nums[l] + nums[r] < target:
l += 1
else:
r -= 1
else:
for i in range(0, len(nums)-N+1): # careful about range
if target < nums[i]*N or target > nums[-1]*N: # take advantages of sorted list
break
if i == 0 or i > 0 and nums[i-1] != nums[i]: # recursively reduce N
self.findNsum(nums[i+1:], target-nums[i], N-1, result+[nums[i]], results)
returnGo solution
matched/originalfunc fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
res := [][]int{}
for i:=0; i<len(nums)-3; i++ {
for i>0 && i<len(nums) && nums[i]==nums[i-1] {
i++
}
for j:=i+1; j<len(nums); j++ {
for j>i+1 && j<len(nums) && nums[j]==nums[j-1] {
j++
}
start:=j+1
end:=len(nums)-1
for start<end {
if (nums[start]+nums[end]+nums[i]+nums[j])<target {
start++
for start< len(nums) && nums[start]==nums[start-1] {
start++
}
} else if (nums[start]+nums[end]+nums[i]+nums[j])>target {
end--
for end>0 && nums[end]==nums[end+1] {
end--
}
} else {
res = append(res, []int{nums[i], nums[j], nums[start], nums[end]})
start++
end--
for start<len(nums) && nums[start]==nums[start-1] {
start++
}
for end>0 && nums[end]==nums[end+1] {
end--
}
}
}
}
}
return res
}Explanation
Метод FourSum:
Этот метод инициализирует основной процесс поиска, создавая список rs для хранения результатов.
Массив nums сортируется для упрощения дальнейшей логики.
Затем вызывается вспомогательный метод Helper с параметрами: результатами, отсортированным массивом, целевым значением, количеством элементов для поиска (в данном случае 4), начальным индексом и пустым списком для временного хранения текущего поднабора.
Метод Helper:
Этот метод рекурсивно находит наборы чисел, которые соответствуют заданному количеству k и суммируются до указанного целевого значения target.
База рекурсии (k == 2): Когда требуется найти пары чисел, функция использует двухуказательный подход. l начинает с начального индекса, r — с конца массива. В цикле проверяется сумма чисел на этих позициях:
Если сумма равна target, текущая пара добавляется в временный список subList, и результат добавляется в основной список rs. После добавления результаты очищаются для следующего возможного набора.
Если сумма меньше target, увеличивается индекс l, чтобы попробовать большее число.
Если сумма больше target, уменьшается индекс r, чтобы попробовать меньшее число.
Рекурсивный вызов (k > 2): При большем количестве элементов для поиска (например, 4) метод перебирает элементы массива начиная с указанного индекса. Для каждого элемента:
Если текущий элемент такой же, как предыдущий, пропускается, чтобы избежать дублирования.
Текущий элемент добавляется в subList, и вызывается рекурсивно с уменьшением k на 1 и обновлением целевого значения (target - nums[i]).
После возвращения из рекурсии элемент удаляется из subList для возможности обработки следующих комбинаций.
Временная и пространственная сложность:
Временная сложность: О(n^3), так как в самом худшем случае каждая из рекурсий может быть вызвана до трех уровней вложенности, где n — длина массива nums.
Пространственная сложность: O(n), включая список для хранения подмножеств и рекурсивный стек.