Leetcode(18) 4Sum

发表于 | 更新于 | 分类于

Description:

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

解法：

虽然难度在递增，但是整体的套路都是一样的，在于如何去除重复项，由于Python中list不可哈希，利用set或dict进行去重时需要先把list转化为tuple，此题的解法和3 Sum基本没啥区别，就是多加了一层for循环，其他的都一样，代码如下：

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
class Solution:
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        nums.sort();
        result = [];
        for i in range(len(nums) - 3):
            for j in range(i +1,len(nums) - 2):
                p = j+1;q = len(nums) - 1;
                while(p<q):
                    sum = nums[i] + nums[j] + nums[p] + nums[q];
                    if(sum == target):
                        tmp = [nums[i],nums[j],nums[p],nums[q]];
                        result.append(tmp);
                        p+=1;
                        q-=1;
                    elif(sum < target):
                        p+=1;
                    else:
                        q-=1;
        r = [];
        for x in result:
            tmp = tuple(x);
            r.append(tmp);
        r = list(set(tuple(r)));
        result =[];
        for x in r:
            tmp = list(x);
            result.append(tmp);
        return result;