18. 4Sum
給定一個包含 n 個整數的數組 nums，返回所有唯一的四元組 [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] == target 你可以按任意順序返回答案。
範例 1：
輸入：nums = [1,0,-1,0,-2,2], target = 0 輸出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Python
from typing import List
class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
nums.sort() # Sort the array to make it easier to skip duplicates and use
two pointers
results = []
n = len(nums)
for i in range(n - 3):
# Skip duplicate values for the first element
if i > 0 and nums[i] == nums[i - 1]:
continue
for j in range(i + 1, n - 2):
# Skip duplicate values for the second element
if j > i + 1 and nums[j] == nums[j - 1]:
continue
left = j + 1
right = n - 1
while left < right:
total = nums[i] + nums[j] + nums[left] + nums[right]
if total == target:
results.append([nums[i], nums[j], nums[left], nums[right]])
# Skip duplicate values for the third and fourth elements
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif total < target:
left += 1
else:
right -= 1
return results
16.50MB, 453ms
C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> results;
sort(nums.begin(), nums.end()); // Sort the array to use the two-pointer
technique
int n = nums.size();
for (int i = 0; i < n - 3; ++i) {
// Skip duplicate values for the first element
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < n - 2; ++j) {
// Skip duplicate values for the second element
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int left = j + 1;
int right = n - 1;
while (left < right) {
long long total = (long long)nums[i] + nums[j] + nums[left] +
nums[right]; // Use long long to avoid overflow
if (total == target) {
results.push_back({nums[i], nums[j], nums[left], nums[right]});
// Skip duplicate values for the third and fourth elements
while (left < right && nums[left] == nums[left + 1]) ++left;
while (left < right && nums[right] == nums[right - 1]) --right;
++left;
--right;
} else if (total < target) {
++left;
} else {
--right;
}
}
}
}
return results;
}
};
15.92MB, 28ms
Javascript
/**
* @param {number[]} nums
* @param {number} target
* @return {number[][]}
*/
var fourSum = function(nums, target) {
const results = [];
if (nums.length < 4) return results;
nums.sort((a, b) => a - b); // Sort the array to use the two-pointer technique
for (let i = 0; i < nums.length - 3; i++) {
// Skip duplicate values for the first element
if (i > 0 && nums[i] === nums[i - 1]) continue;
for (let j = i + 1; j < nums.length - 2; j++) {
// Skip duplicate values for the second element
if (j > i + 1 && nums[j] === nums[j - 1]) continue;
let left = j + 1;
let right = nums.length - 1;
while (left < right) {
const total = nums[i] + nums[j] + nums[left] + nums[right];
if (total === target) {
results.push([nums[i], nums[j], nums[left], nums[right]]);
// Skip duplicate values for the third and fourth elements
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
left++;
right--;
} else if (total < target) {
left++;
} else {
right--;
}
}
}
}
return results;
};
52.81MB, 90ms
