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循环，其他的都一样，代码如下：

class :
    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;

leetcode(18) 4sum 解法：

解法：

近期文章

近期评论

标签

热门

文章归档

分类目录

功能