[已解决]Python：【新】每日一题 1

liuzhengyuan

专辑说明

今天的题目：

给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。

注意：答案中不可以包含重复的四元组。

请封装成一个函数，nums 和 target 为函数参数

示例 1：

输入：nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]

示例 2：

输入：nums = [], target = 0
输出：[]

欢迎大家来答题

来源：力扣（LeetCode）

最佳答案

月排行榜 / 总排行榜

crisfo

2021-3-18 15:44:56

def test(nums, target):
    t = []
    length = len(nums)
    if length < 4:
        print('error nums')
        return t

    nums.sort()

    for i in range(length-3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, length-2):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            left = j+1
            right = length-1
            while left < right:
                sum = nums[i] + nums[j] + nums[left] + nums[right]
                if target == sum:
                    t.append([nums[i],nums[j],nums[left],nums[right]])

                    while left < right and nums[left] == nums[left+1]:
                        left+=1
                    while left < right and nums[right] == nums[right-1]:
                        right-=1
                    left+=1
                    right-=1
                elif target < sum:
                    right-=1
                else:
                    left+=1
    return t

nums = [3, -1, 4, -3, -2, 1, 2, -4]
target = 0
list1 = test(nums, target)
print(list1)

测试结果

[[-4, -3, 3, 4], [-4, -2, 2, 4], [-4, -1, 1, 4], [-4, -1, 2, 3], [-3, -2, 1, 4], [-3, -2, 2, 3], [-3, -1, 1, 3], [-2, -1, 1, 2]]

跳转到最佳答案楼层

liuzhengyuan

挺难的……

洋洋痒

我认输

liuzhengyuan

洋洋痒 发表于 2021-3-17 20:25
我认输

下次会简单一点

洋洋痒

def s(nums,target):
    nums=sorted(nums)
    L=[]
    for i in range(len(nums)-3):
        for j in range(i+1,len(nums)-2):
            for k in range(j+1,len(nums)-1):
                for l in range(k+1,len(nums)):
                    if nums[i]+nums[j]+nums[k]+nums[l]==target and [nums[i],nums[j],nums[k],nums[l]] not in L:
                        L.append([nums[i],nums[j],nums[k],nums[l]])
    return L
L=s([1,0,-1,0,-2,2],0)
print(L)

liuzhengyuan

洋洋痒 发表于 2021-3-17 20:52

输入

[91277418,66271374,38763793,4092006,11415077,60468277,1122637,72398035,-62267800,22082642,60359529,-16540633,92671879,-64462734,-55855043,-40899846,88007957,-57387813,-49552230,-96789394,18318594,-3246760,-44346548,-21370279,42493875,25185969,83216261,-70078020,-53687927,-76072023,-65863359,-61708176,-29175835,85675811,-80575807,-92211746,44755622,-23368379,23619674,-749263,-40707953,-68966953,72694581,-52328726,-78618474,40958224,-2921736,-55902268,-74278762,63342010,29076029,58781716,56045007,-67966567,-79405127,-45778231,-47167435,1586413,-58822903,-51277270,87348634,-86955956,-47418266,74884315,-36952674,-29067969,-98812826,-44893101,-22516153,-34522513,34091871,-79583480,47562301,6154068,87601405,-48859327,-2183204,17736781,31189878,-23814871,-35880166,39204002,93248899,-42067196,-49473145,-75235452,-61923200,64824322,-88505198,20903451,-80926102,56089387,-58094433,37743524,-71480010,-14975982,19473982,47085913,-90793462,-33520678,70775566,-76347995,-16091435,94700640,17183454,85735982,90399615,-86251609,-68167910,-95327478,90586275,-99524469,16999817,27815883,-88279865,53092631,75125438,44270568,-23129316,-846252,-59608044,90938699,80923976,3534451,6218186,41256179,-9165388,-11897463,92423776,-38991231,-6082654,92275443,74040861,77457712,-80549965,-42515693,69918944,-95198414,15677446,-52451179,-50111167,-23732840,39520751,-90474508,-27860023,65164540,26582346,-20183515,99018741,-2826130,-28461563,-24759460,-83828963,-1739800,71207113,26434787,52931083,-33111208,38314304,-29429107,-5567826,-5149750,9582750,85289753,75490866,-93202942,-85974081,7365682,-42953023,21825824,68329208,-87994788,3460985,18744871,-49724457,-12982362,-47800372,39958829,-95981751,-71017359,-18397211,27941418,-34699076,74174334,96928957,44328607,49293516,-39034828,5945763,-47046163,10986423,63478877,30677010,-21202664,-86235407,3164123,8956697,-9003909,-18929014,-73824245]
-236727523

超出时间限制

yayc_zcyd

Python每日一题由你来承担了

洋洋痒

liuzhengyuan 发表于 2021-3-17 21:52
输入
超出时间限制

再次认输

Stubborn

我们先对nums进行排序， 首先确定几个思想。

1.当我们确定第一个数 a1 之后，若 a1 之后的三个数之和大于 target 。 那么 a1 之后的所有组合，都会大于target 。
同理当我们确定第一个数 a1 之后，，若 a1 与nums的末尾的三个数之和小鱼于 target 。 那么 a1 之后的所有组合，都会小于target 。

nums[i] + nums[i+1] + nums[i+2] + nums[i+3] >  target
nums[i] + nums[j] + nums[j-1] + nums[j-2] >  target

2.当我们确定两个数 ai aj ,  若 aj 之后的两个数之和大于 target 。 那么 ai, aj 之后的所有组合，都会大于target 。
同理，当我们确定两个数 ai aj ,  若 ai aj 与 nums 的末尾的两个个数之和小于 target 。 那么 ai aj 之后的所有组合，都会小于target 。

3.最后当我们确定两个数之后，此时我们的问题变成了，从num[ j : n ] 寻找两数之和，使用双指针，或者二分加快效率

crisfo

def test(nums, target):
    t = []
    length = len(nums)
    if length < 4:
        print('error nums')
        return t

    nums.sort()

    for i in range(length-3):
        if i > 0 and nums[i] == nums[i-1]:
            continue
        for j in range(i+1, length-2):
            if j > i+1 and nums[j] == nums[j-1]:
                continue
            left = j+1
            right = length-1
            while left < right:
                sum = nums[i] + nums[j] + nums[left] + nums[right]
                if target == sum:
                    t.append([nums[i],nums[j],nums[left],nums[right]])

                    while left < right and nums[left] == nums[left+1]:
                        left+=1
                    while left < right and nums[right] == nums[right-1]:
                        right-=1
                    left+=1
                    right-=1
                elif target < sum:
                    right-=1
                else:
                    left+=1
    return t

nums = [3, -1, 4, -3, -2, 1, 2, -4]
target = 0
list1 = test(nums, target)
print(list1)

测试结果

[[-4, -3, 3, 4], [-4, -2, 2, 4], [-4, -1, 1, 4], [-4, -1, 2, 3], [-3, -2, 1, 4], [-3, -2, 2, 3], [-3, -1, 1, 3], [-2, -1, 1, 2]]

sdhmlsq

高手啊。学习

liuzhengyuan

crisfo 发表于 2021-3-18 15:44
测试结果

616ms，通过

私はり

好难啊

liuzhengyuan

---------------已结帖--------------------之后的回答不会有积分奖励

jerryxjr1220

随便写写，没有考虑优化，纯粹穷举。
写个递归

def main(nums, target):
    result = []
    def digui(nums: list, target: int, m, candi: list = [[]]):
        if m == 1:
            for i in nums:
                for each in candi:
                    if i+sum(each) == target:
                        output = sorted(each+[i])
                        if output not in result:
                            result.append(output)
        else:
            for i in range(len(nums)):
                new_nums = nums.copy()
                new_nums.pop(i)
                new_candi = []
                for each in candi:
                    if nums[i]+sum(each)<=target:
                        new_candi.append(each+[nums[i]])
                digui(new_nums, target, m-1, new_candi)
    digui(nums, target, 4)
    result.sort()
    return result

print(main([3, -1, 4, -3, -2, 1, 2, -4], 0))

[[-4, -3, 3, 4], [-4, -2, 2, 4], [-4, -1, 1, 4], [-4, -1, 2, 3], [-3, -2, 1, 4], [-3, -2, 2, 3], [-3, -1, 1, 3], [-2, -1, 1, 2]]

qq1151985918

def find(List,target):
    l = len(List)
    if l < 4:
        return False
    res = []
    for a in range(l):
        for b in range(a + 1,l):
            for c in range(b + 1,l):
                for d in range(c + 1,l):
                    if List[a] + List[b] + List[c] + List[d] == target:
                        res.append([List[a],List[b],List[c],List[d]])
    return res

print(find([3, -1, 4, -3, -2, 1, 2, -4],0))
print("-" * 8)
print(find([3, -1, 4, -3, -2, 1, 2, -4],1))