Sort in Ascending order, traverse using two pointers by binary search and store the answer in a mutable array to solve "18. 4Sum"
Example
18. 4Sum
Given an array nums of n integers, return an array of all the unique quadruplets [nums[a], nums[b], nums[c], nums[d]] such that:
0 <= a, b, c, d < n
a, b, c, and d are distinct.
nums[a] + nums[b] + nums[c] + nums[d] == target
You may return the answer in any order.
Example 1:
Input: nums = [1,0,-1,0,-2,2], target = 0
Output: [[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
Answers
Note: the number will exceed maxmium of integer, use long type instead.
java c# c++ c are same:
long total = (long) nums[i] + nums[j] + nums[l] + nums[r];Double Pointer and Binary Search
var fourSum = function(nums, target) {
const n = nums.length, 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 l = j + 1, r = n - 1
while (l < r) {
const total = nums[i] + nums[j] + nums[l] + nums[r]
if (total >= target) {
if (total === target) {
ans.push([nums[i], nums[j], nums[l], nums[r]])
while (nums[l] === nums[l + 1]) l++
while (nums[r] === nums[r - 1]) r--
}
r--
} else l++
}
}
}
return ans
};function fourSum(nums: number[], target: number): number[][] {
const n = nums.length, 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 l = j + 1, r = n - 1
while (l < r) {
const total = nums[i] + nums[j] + nums[l] + nums[r]
if (total >= target) {
if (total === target) {
ans.push([nums[i], nums[j], nums[l], nums[r]])
while (nums[l] === nums[l + 1]) l++
while (nums[r] === nums[r - 1]) r--
}
r--
} else {
l++
}
}
}
}
return ans
};func fourSum(nums []int, target int) [][]int {
sort.Ints(nums)
n, ans := len(nums), [][]int{}
for i := 0; i < n - 3; i++ {
if i > 0 && nums[i] == nums[i - 1] {
continue
}
for j := i + 1; j < n - 2; j++ {
if j > i + 1 && nums[j] == nums[j - 1] {
continue
}
l, r := j + 1, n - 1
for l < r {
total := nums[i] + nums[j] + nums[l] + nums[r]
if total >= target {
if total == target {
ans = append(ans, []int{nums[i], nums[j], nums[l], nums[r]})
for r > l && nums[r] == nums[r - 1] {
r--
}
for l < r && nums[l] == nums[l + 1] {
l++
}
}
r--
} else {
l++
}
}
}
}
return ans
}class Solution {
function fourSum($nums, $target) {
$ans = [];
$n = count($nums);
sort($nums, SORT_NUMERIC);
for ($i = 0; $i < $n - 3; $i++) {
if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue;
for ($j = $i + 1; $j < $n - 2; $j++) {
if ($j > $i + 1 && $nums[$j] === $nums[$j - 1]) continue;
$l = $j + 1;
$r = $n - 1;
while ($l < $r) {
$total = $nums[$i] + $nums[$j] + $nums[$l] + $nums[$r];
if ($total >= $target) {
if ($total === $target) {
$ans []= [$nums[$i], $nums[$j], $nums[$l], $nums[$r]];
while ($r > $l && $nums[$r] === $nums[$r - 1]) $r--;
while ($l < $r && $nums[$l] === $nums[$l + 1]) $l++;
}
$r--;
} else {
$l++;
}
}
}
}
return $ans;
}
}class Solution {
public List<List<Integer>> fourSum(int[] nums, int target) {
int n = nums.length;
List<List<Integer>> ans = new ArrayList<List<Integer>>();
Arrays.sort(nums);
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;
int l = j + 1, r = n - 1;
while (l < r) {
long total = (long) nums[i] + nums[j] + nums[l] + nums[r];
if (total >= target) {
if (total == target) {
ans.add(Arrays.asList(nums[i], nums[j], nums[l], nums[r]));
while (r > l && nums[r] == nums[r - 1]) r--;
while (l < r && nums[l] == nums[l + 1]) l++;
}
r--;
} else {
l++;
}
}
}
}
return ans;
}
}public class Solution {
public IList<IList<int>> FourSum(int[] nums, int target) {
int n = nums.Length;
IList<IList<int>> ans = new List<IList<int>>();
Array.Sort(nums);
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;
int l = j + 1, r = n - 1;
while (l < r) {
long total = (long) nums[i] + nums[j] + nums[l] + nums[r];
if (total >= target) {
if (total == target) {
ans.Add(new List<int>{nums[i], nums[j], nums[l], nums[r]});
while (r > l && nums[r] == nums[r - 1]) r--;
while (l < r && nums[l] == nums[l + 1]) l++;
}
r--;
} else {
l++;
}
}
}
}
return ans;
}
}class Solution {
public:
vector<vector<int>> fourSum(vector<int>& nums, int target) {
int n = nums.size();
vector<vector<int>> ans;
sort(nums.begin(), nums.end());
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;
int l = j + 1, r = n - 1;
while (l < r) {
long total = (long) nums[i] + nums[j] + nums[l] + nums[r];
if (total >= target) {
if (total == target) {
ans.push_back(vector<int>{nums[i], nums[j], nums[l], nums[r]});
while (r > l && nums[r] == nums[r - 1]) r--;
while (l < r && nums[l] == nums[l + 1]) l++;
}
r--;
} else {
l++;
}
}
}
}
return ans;
}
};const static inline int cmp(const void *pa, const void *pb) {
return *(int *)pa - *(int *)pb;
}
int** fourSum(int* nums, int numsSize, int target, int* returnSize, int** returnColumnSizes){
qsort(nums, numsSize, sizeof(int), cmp);
int** ans = malloc(sizeof(int*) * numsSize * numsSize);
*returnColumnSizes = malloc(sizeof(int) * numsSize * numsSize);
int pos = 0;
for (int i = 0; i < numsSize - 3; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue;
for (int j = i + 1; j < numsSize - 2; j++) {
if (j > i + 1 && nums[j] == nums[j - 1]) continue;
int l = j + 1, r = numsSize - 1;
while (l < r) {
long total = (long) nums[i] + nums[j] + nums[l] + nums[r];
if (total >= target) {
if (total == target) {
int* tmp = malloc(sizeof(int) * 4);
tmp[0] = nums[i];
tmp[1] = nums[j];
tmp[2] = nums[l];
tmp[3] = nums[r];
ans[pos] = tmp;
(*returnColumnSizes)[pos] = 4;
pos++;
while (r > l && nums[r] == nums[r - 1]) r--;
while (l < r && nums[l] == nums[l + 1]) l++;
}
r--;
} else {
l++;
}
}
}
}
*returnSize = pos;
return ans;
}class Solution:
def fourSum(self, nums: List[int], target: int) -> List[List[int]]:
n, ans = len(nums), []
nums.sort()
for i in range(0, n - 3):
if i > 0 and nums[i] == nums[i - 1]: continue
for j in range(i + 1, n - 2):
if j > i + 1 and nums[j] == nums[j - 1]: continue
l, r = j + 1, n - 1
while l < r:
total = nums[i] + nums[j] + nums[l] + nums[r]
if total >= target:
if total == target:
ans.append([nums[i], nums[j], nums[l], nums[r]])
while r > l and nums[r] == nums[r - 1]: r -= 1
while l < r and nums[l] == nums[l + 1]: l += 1
r -= 1
else: l += 1
return ans