Array
Sorting
Two Pointers
Description
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 < na, 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]]
Example 2:
Input: nums = [2,2,2,2,2], target = 8
Output: [[2,2,2,2]]
Constraints:
1 <= nums.length <= 200-109 <= nums[i] <= 109 -109 <= target <= 109
Solutions
Solution 1: Sorting + Double Pointers
We notice that the problem requires us to find non-repeating quadruplets. Therefore, we can first sort the array, which makes it easy to skip duplicate elements.
Next, we enumerate the first two elements of the quadruplet, \(nums[i]\) and \(nums[j]\) , where \(i \lt j\) . During the enumeration process, we skip duplicate \(nums[i]\) and \(nums[j]\) . Then, we use two pointers \(k\) and \(l\) to point to the two ends behind \(nums[i]\) and \(nums[j]\) . Let \(x = nums[i] + nums[j] + nums[k] + nums[l]\) , we compare \(x\) with \(target\) and perform the following operations:
If \(x \lt target\) , then update \(k = k + 1\) to get a larger \(x\) ;
If \(x \gt target\) , then update \(l = l - 1\) to get a smaller \(x\) ;
Otherwise, it means that a quadruplet \((nums[i], nums[j], nums[k], nums[l])\) is found. Add it to the answer, then we update the pointers \(k\) and \(l\) , and skip all duplicate elements to prevent the answer from containing duplicate quadruplets, and continue to find the next quadruplet.
The time complexity is \(O(n^3)\) , and the space complexity is \(O(\log n)\) . Here, \(n\) is the length of the array.
Python3 Java C++ Go TypeScript JavaScript C# PHP
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 class Solution :
def fourSum ( self , nums : List [ int ], target : int ) -> List [ List [ int ]]:
n = len ( nums )
ans = []
if n < 4 :
return ans
nums . sort ()
for i in range ( n - 3 ):
if i 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
k , l = j + 1 , n - 1
while k < l :
x = nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ]
if x < target :
k += 1
elif x > target :
l -= 1
else :
ans . append ([ nums [ i ], nums [ j ], nums [ k ], nums [ l ]])
k , l = k + 1 , l - 1
while k < l and nums [ k ] == nums [ k - 1 ]:
k += 1
while k < l and nums [ l ] == nums [ l + 1 ]:
l -= 1
return ans
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 class Solution {
public List < List < Integer >> fourSum ( int [] nums , int target ) {
int n = nums . length ;
List < List < Integer >> ans = new ArrayList <> ();
if ( n < 4 ) {
return ans ;
}
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 k = j + 1 , l = n - 1 ;
while ( k < l ) {
long x = ( long ) nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ] ;
if ( x < target ) {
++ k ;
} else if ( x > target ) {
-- l ;
} else {
ans . add ( List . of ( 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 ;
}
}
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 class Solution {
public :
vector < vector < int >> fourSum ( vector < int >& nums , int target ) {
int n = nums . size ();
vector < vector < int >> ans ;
if ( n < 4 ) {
return ans ;
}
sort ( nums . begin (), nums . end ());
for ( int i = 0 ; i < n - 3 ; ++ i ) {
if ( i && 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 k = j + 1 , l = n - 1 ;
while ( k < l ) {
long long x = ( long long ) nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ];
if ( x < target ) {
++ k ;
} else if ( x > target ) {
-- l ;
} else {
ans . push_back ({ 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 ;
}
};
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 func fourSum ( nums [] int , target int ) ( ans [][] int ) {
n := len ( nums )
if n < 4 {
return
}
sort . Ints ( nums )
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
}
k , l := j + 1 , n - 1
for k < l {
x := nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ]
if x < target {
k ++
} else if x > target {
l --
} else {
ans = append ( ans , [] int { nums [ i ], nums [ j ], nums [ k ], nums [ l ]})
k ++
l --
for k < l && nums [ k ] == nums [ k - 1 ] {
k ++
}
for k < l && nums [ l ] == nums [ l + 1 ] {
l --
}
}
}
}
}
return
}
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 function fourSum ( nums : number [], target : number ) : number [][] {
const n = nums . length ;
const ans : number [][] = [];
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 ;
}
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
40
41 /**
* @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 ;
};
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 public class Solution {
public IList < IList < int >> FourSum ( int [] nums , int target ) {
int n = nums . Length ;
var ans = new List < IList < int >> ();
if ( n < 4 ) {
return ans ;
}
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 k = j + 1 , l = n - 1 ;
while ( k < l ) {
long x = ( long ) nums [ i ] + nums [ j ] + nums [ k ] + nums [ l ];
if ( x < target ) {
++ k ;
} else if ( x > target ) {
-- l ;
} else {
ans . Add ( new List < int > { 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 ;
}
}
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
40
41
42
43
44
45
46
47
48
49
50
51
52
53 class Solution {
/**
* @param int[] $nums
* @param int $target
* @return int[][]
*/
function fourSum($nums, $target) {
$result = [];
$n = count($nums);
sort($nums);
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;
}
$left = $j + 1;
$right = $n - 1;
while ($left < $right) {
$sum = $nums[$i] + $nums[$j] + $nums[$left] + $nums[$right];
if ($sum === $target) {
$result[] = [$nums[$i], $nums[$j], $nums[$left], $nums[$right]];
while ($left < $right && $nums[$left] === $nums[$left + 1]) {
$left++;
}
while ($left < $right && $nums[$right] === $nums[$right - 1]) {
$right--;
}
$left++;
$right--;
} elseif ($sum < $target) {
$left++;
} else {
$right--;
}
}
}
}
return $result;
}
}
