18. 4Sum

发表于 | 分类于 | 阅读次数
字数统计 623 | 阅读时长 3

18. 4Sum

       Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target ? Find all unique quadruplets in the array which gives the sum of target.

       Note : The solution set must not contain duplicate quadruplets.

For example, given array S = [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]
]

思路

  • 对数组排序
  • 确定四元数中的前两个（a，b）
  • 遍历剩余数组确定两外两个（c，d），确定cd时思路跟3Sum确定后两个数据一样，二分查找左右逼近。
  • 在去重时采用set集合

问题

       第一次提交自己写的如下代码也会超时，主要原因是在每层循环的时候都调用nums.size()会造成很多的时间浪费，因为其是一个不变的值，所以应该初始化的时候直接把他付给一个整形变量，后面就不会再重复调用nums.size()了，降低时间复杂度

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
class Solution {
public:
	vector<vector<int>> fourSum(vector<int>& nums, int target) {
		set<vector<int>> res2;
		vector<vector<int>> res;
		sort(nums.begin(), nums.end());
		int len = nums.size();
		for (int i = 0;i<len-3;i++)
		{
			for (int j = i+1;j<len-2;j++)
			{
			   int pre = j + 1;
			   int tail = len - 1;
			   while (pre < tail)
			   {
				   vector<int> tempRes;
				   int sum = nums[i] + nums[j] + nums[pre] + nums[tail];
				   if (sum == target)
				   {
					   tempRes.push_back(nums[i]);
					   tempRes.push_back(nums[j]);
					   tempRes.push_back(nums[pre]);
					   tempRes.push_back(nums[tail]);
					   res2.insert(tempRes);
					   pre++;
					   tail--;
				   }
				   else if (sum < target)
				   {
					   pre++;
				   }
				   else
					   tail--;
			   }
			}
		}
		for (auto r : res2)
		{
			res.push_back(r);
		}
		return res;
	}
};
int main()
{
	vector<int> s = { -3,-2,-1,0,0,1,2,3 };
	int target = 0;
	Solution3 ss;
	auto res = ss.fourSum(s, target);
	system("pause");
	return 0;
}

　Java Code：

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
class Solution {
    public List<List<Integer>> fourSum(int[] nums, int target) {

        if (null == nums) {
            return new ArrayList();
        }

        int len = nums.length;
        if (len == 0) {
            return new ArrayList();
        }
        Arrays.sort(nums);
        Set<List<Integer>> resSet = new HashSet();
        //-2 -1  0 0 1 2
        for (int i = 0;i < len -3;i++) {
            for (int j = i + 1;j < len -2;j++) {
                int pre = j + 1;
                int tail = len -1;

                while (pre < tail) {

                    List<Integer> res = new ArrayList();
                    int sum = nums[i] + nums[j] + nums[pre] + nums[tail];
                    //System.out.println("i:" + i + ",j:" + j + ",pre:" + pre + ",tail:" + tail);
                    //System.out.println(sum);
                    if (target == sum) {
                        res.add(nums[i]);
                        res.add(nums[j]);
                        res.add(nums[pre]);
                        res.add(nums[tail]);
                        resSet.add(res);
                        //System.out.println(res);
                        pre++;
                        tail--;
                    } else if (sum < target) {
                        pre++;
                    } else {
                        tail--;
                    }
                }

            }
        }

        return resSet.stream().collect(Collectors.toList());
    }
}