18. 4Sum

发表于 | 分类于

每日一题 2019 - 03 - 09

题目：

Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums 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.

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]
]

解法：

这个题让我们找出给定数组中某四个数字的和等于目标值的序列，基本想法跟leetcode 15.3Sum一致，唯一需要注意的一点就是这个题需要用到三重循环，所用时间复杂度变成O(n^3)，同时需要注意外层指针要在末尾前3个位置停止更新，谨防越界。

代码：

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
54
55
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        int size = nums.size();
        sort(nums.begin(),nums.end());
        vector<vector<int>> test ;
        if(size <=2 )
        {
            return test ;
        }
        for(int j = 0 ; j < size - 3  ; j ++ )
        {
            int target_temp = target - nums[j] ;
            for(int i = j + 1 ; i < size - 2 ; i ++ )
            {
                int left = i + 1 ; 
                int right = size - 1 ;
                vector<int> temp ;
                while (left < right){    
                    if(nums[i] + nums[left] + nums[right] < target_temp )
                    {
                        left ++ ;
                    }
                    else if(nums[i] + nums[left] + nums[right] > target_temp )
                    {
                        right -- ;
                    }
                    else
                    {
                        temp.push_back(nums[j]);
                        temp.push_back(nums[i]);
                        temp.push_back(nums[left]);
                        temp.push_back(nums[right]);
                        test.push_back(temp);
                        temp.clear();
                        while(nums[left] == nums[left+1] && ( left < size - 2 ) )
                        {
                            left ++ ;
                        }
                        left ++ ;
                    }
                }
                while(nums[i] == nums[i+1] && ( i < size - 2 ))
                {
                   i ++ ;
                }
            }
            while(nums[j] == nums[j+1] && j < size -3 )
            {
                j ++ ;
            }
        }
        return test ;
    }
};
0%
undefined