本文共 1127 字,大约阅读时间需要 3 分钟。
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] ] 题意:在数组S中找到四个元素相加和为0,当然要去重 思路:采用快速排序法只排一次,每次取一个数x,问题转化为target-x的3sum问题 时间复杂度为O(n^3) 第一个:每次取一个数,只将该元素后续的列表中查找target-x的3sum和; 第二个:每次取一个数,需要判断是否和前一个数重复(循环起始数除外),只有不重复才进行3sum计算,重复则continue 3sum计算同理,就能避免重复 第三个:在进行2sum计算,若2sum的和等于target后,需要将左右指针移位,过滤后续重复元素,直到元素不重复再计算2sum之和 Runtime: 892 msclass Solution(object): def fourSum(self, nums, target): if len(nums)<=3: return [] nums=sorted(nums) four=[] for i in range(0,len(nums)-3): if nums[i]==nums[i-1] and i!=0: continue for j in range(i+1,len(nums)-2): if nums[j]==nums[j-1] and j!=i+1: continue t=target-nums[i]-nums[j] l,r=j+1,len(nums)-1 while l
转载地址:http://pcfin.baihongyu.com/