18. 4Sum
0 <= a, b, c, d < n
a, b, c и d различны.
nums[a] + nums[b] + nums[c] + nums[d] == цель
Вы можете вернуть ответ в любом порядке.
C# 解法
匹配/原始public 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++ 解法
自动草稿，提交前请检查#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 解法
匹配/原始public 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 解法
匹配/原始/**
* @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 解法
匹配/原始def 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 解法
匹配/原始func 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
}Метод FourSum:
Этот метод инициализирует основной процесс поиска, создавая список rs для хранения результатов.
数组 nums сортируется для упрощения дальнейшей логики.
Затем вызывается вспомогательный метод Helper с параметрами: результатами, отсортированным 数组ом, целевым значением, количеством elementов для поиска (в данном случае 4), начальным индексом и пустым списком для временного хранения текущего поднабора.
Метод Helper:
Этот метод рекурсивно находит наборы чисел, которые соответствуют заданному количеству k и суммируются до указанного целевого значения target.
База рекурсии (k == 2): Когда it is required find пары чисел, функция использует двухуказательный подход. l начинает с начального индекса, r — с конца 数组а. В цикле проверяется сумма чисел на этих позициях:
Если сумма равна target, текущая пара добавляется в временный список subList, и результат добавляется в основной список rs. После добавления результаты очищаются для следующего возможного набора.
Если сумма меньше target, увеличивается индекс l, чтобы попробовать большее number.
Если сумма больше target, уменьшается индекс r, чтобы попробовать меньшее number.
Рекурсивный вызов (k > 2): При большем количестве elementов для поиска (на示例, 4) метод перебирает elementы 数组а начиная с указанного индекса. Для каждого elementа:
Если текущий element такой же, как предыдущий, пропускается, чтобы избежать дублирования.
Текущий element добавляется в subList, и вызывается рекурсивно с уменьшением k на 1 и обновлением целевого значения (target - nums[i]).
После возвращения из рекурсии element удаляется из subList для возможности обработки следующих комбинаций.
Временная и пространственная Complexity:
Временная Complexity: О(n^3), так как в самом худшем случае каждая из рекурсий может быть вызвана до трех уровней вложенности, где n — длина 数组а nums.
Пространственная Complexity: O(n), включая список для хранения подмножеств и рекурсивный стек.
Vacancies for this task
活跃职位 with overlapping task tags are 已显示.