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

liuzhengyuan · 发表于 2021-3-17 19:32:51

马上注册，结交更多好友，享用更多功能^_^

您需要登录才可以下载或查看，没有账号？立即注册

x

本帖最后由 liuzhengyuan 于 2021-3-17 19:37 编辑

专辑说明

今天的题目：

给定一个包含 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 · 发表于 2021-3-17 20:06:38

挺难的……

洋洋痒 · 发表于 2021-3-17 20:25:56

我认输

liuzhengyuan · 发表于 2021-3-17 20:43:43

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

下次会简单一点

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

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 21:52:41

洋洋痒发表于 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 · 发表于 2021-3-17 22:02:14

Python每日一题由你来承担了

洋洋痒 · 发表于 2021-3-17 22:07:43

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

再次认输

Stubborn · 发表于 2021-3-18 00:27:45

本帖最后由 Stubborn 于 2021-3-18 00:41 编辑

我们先对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 · 发表于 2021-3-18 15:44:56

这个最佳答案由 crisfo 给出，感谢 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 · 发表于 2021-3-18 15:58:48

高手啊。学习

liuzhengyuan · 发表于 2021-3-18 17:26:48

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

616ms，通过

私はり · 发表于 2021-3-18 19:59:02

好难啊

liuzhengyuan · 发表于 2021-3-19 16:21:56

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

jerryxjr1220 · 发表于 2021-3-19 19:18:07

本帖最后由 jerryxjr1220 于 2021-3-19 19:29 编辑

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

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 · 发表于 2021-3-20 08:28:42

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

复制代码

账号		自动登录	找回密码
密码			立即注册

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

马上注册，结交更多好友，享用更多功能^_^

本帖被以下淘专辑推荐:

评分

评分

评分

浏览过的版块