GuilinDev

Lc0018

05 August 2008

18 - 4Sum

原题概述

Given an array 

1

nums
of n integers and an integer 
1

target
, are there elements a, b, c, and d in 
1

nums
such that a + b + c + d = 
1

target
? Find all unique quadruplets in the array which gives the sum of 
1

target
.

Note:

The solution set must not contain duplicate quadruplets.

Example:

1
2
3
4
5
6
7
8

Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

题意和分析

找到Quadruplets的四个数，加起来等于target的值，思路跟3Sum一样，再在外面套一层循环，最后的解决方案不能有重复，所以依然得去重。

时间复杂度: O(nlogn) + O(n^3) = O(n^3)；空间复杂度O(n)。

代码

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

class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {
        ArrayList<List<Integer>> result = new ArrayList<List<Integer>>();
        HashSet<ArrayList<Integer>> noDuplicateQuad = new HashSet<ArrayList<Integer>>();
        
        Arrays.sort(nums);
        
        for (int first = 0; first <= nums.length - 4; first++) {
            for (int second = first + 1; second <= nums.length - 3; second++) {
                int third = second + 1;
                int fourth = nums.length - 1;
                
                while (third < fourth) {
                    int sum = nums[first] + nums[second] + nums[third] + nums[fourth];
                    if (sum < target) {
                        third++;
                    } else if (sum > target) {
                        fourth--;
                    } else { //找到了一个合适的Quadruplet
                        ArrayList<Integer> oneQuadruplet = new ArrayList<>();
                        oneQuadruplet.add(nums[first]);
                        oneQuadruplet.add(nums[second]);
                        oneQuadruplet.add(nums[third]);
                        oneQuadruplet.add(nums[fourth]);
                        
                        if (!noDuplicateQuad.contains(oneQuadruplet)) {
                            noDuplicateQuad.add(oneQuadruplet);
                            result.add(oneQuadruplet);
                        }
                        
                        //这里是两个indices同时移动，因为排过序了后找到的是已经等于target了，所以只移动一个index的话是不会再找到非重复的Quadruplet的
                        third++;
                        fourth--;
                    }
                }
            }
        }
        return result;
    }
}
This site is open source. Improve this page.