4 Sum

Posted on | In , , |

Question

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.

1
2
3
4
5
6
7
8
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]
]

Analysis

这道题相当于是前面3 sum的一个升级，只是多了一个元素，解是思路上还是一个，多一个外层的循环，然后就可以把问题简化成3 sum

Solution

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
class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int> > res;
        int size = nums.size();
        if (size < 4) return res;
        sort(nums.begin(), nums.end());
        for (int i=0; i < size-3; ++i) {
            if (nums[i]+nums[i+1]+nums[i+2]+nums[i+3] > target) break;
            if (nums[i]+nums[size-3]+nums[size-2]+nums[size-1] < target) continue;
            if (i>0 && nums[i-1] == nums[i]) continue;
            for (int j =i+1; j<size-2; ++j) {
                if (j>i+1 && nums[j-1] == nums[j]) continue;
                int sum = target - nums[i]-nums[j];
                int l = j+1, h=size-1;
                while(l < h) {
                    if (nums[l] + nums[h] == sum) {
                        res.push_back({nums[i], nums[j], nums[l], nums[h]});
                        while(nums[l] == nums[++l]);
                    } else if (nums[l]+nums[h] < sum) l++;
                    else --h;
                }
            }
        }
        return res;
    }
};

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
class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort()
        n, res = len(nums), []
        for i in range(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]: # need > i+1 cannot be > 0
                    continue
                s, e, sum = j+1, n-1, target - nums[i] - nums[j]
                while s < e:
                    if nums[s] + nums[e] == sum:
                        res.append([nums[i], nums[j], nums[s], nums[e]])
                        s += 1
                        while s < e and nums[s] == nums[s-1]: # need s < e
                            s += 1
                    elif nums[s] + nums[e] < sum:
                        s+=1
                    else:
                        e -=1
        return res