Python：【新】每日一题 1
本帖最后由 liuzhengyuan 于 2021-3-17 19:37 编辑专辑说明
今天的题目：
给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。
注意：答案中不可以包含重复的四元组。
请封装成一个函数，nums 和 target 为函数参数
示例 1：
输入：nums = , target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：
输入：nums = [], target = 0
输出：[]
欢迎大家来答题{:10_298:}
来源：力扣（LeetCode） 挺难的……{:10_245:} 我认输 洋洋痒 发表于 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+nums+nums+nums==target and ,nums,nums,nums] not in L:
L.append(,nums,nums,nums])
return L
L=s(,0)
print(L)
洋洋痒 发表于 2021-3-17 20:52
{:10_245:}输入
-236727523超出时间限制 Python每日一题由你来承担了{:10_257:} liuzhengyuan 发表于 2021-3-17 21:52
输入
超出时间限制
再次认输{:10_297:} 本帖最后由 Stubborn 于 2021-3-18 00:41 编辑
我们先对nums进行排序， 首先确定几个思想。
1.当我们确定第一个数 a1 之后，若 a1 之后的三个数之和大于 target 。 那么 a1 之后的所有组合，都会大于target 。
同理当我们确定第一个数 a1 之后，，若 a1 与nums的末尾的三个数之和小鱼于 target 。 那么 a1 之后的所有组合，都会小于target 。
nums + nums + nums + nums >target
nums + nums + nums + nums >target
2.当我们确定两个数 ai aj ,若 aj 之后的两个数之和大于 target 。 那么 ai, aj 之后的所有组合，都会大于target 。
同理，当我们确定两个数 ai aj ,若 ai aj 与 nums 的末尾的两个个数之和小于 target 。 那么 ai aj 之后的所有组合，都会小于target 。
3.最后当我们确定两个数之后，此时我们的问题变成了，从num[ j : n ] 寻找两数之和，使用双指针，或者二分加快效率 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 == nums:
continue
for j in range(i+1, length-2):
if j > i+1 and nums == nums:
continue
left = j+1
right = length-1
while left < right:
sum = nums + nums + nums + nums
if target == sum:
t.append(,nums,nums,nums])
while left < right and nums == nums:
left+=1
while left < right and nums == nums:
right-=1
left+=1
right-=1
elif target < sum:
right-=1
else:
left+=1
return t
nums =
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]] 高手啊。学习 crisfo 发表于 2021-3-18 15:44
测试结果
616ms，通过 好难啊
---------------已结帖--------------------之后的回答不会有积分奖励 本帖最后由 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+)
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+sum(each)<=target:
new_candi.append(each+])
digui(new_nums, target, m-1, new_candi)
digui(nums, target, 4)
result.sort()
return result
print(main(, 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]]
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 + List + List + List == target:
res.append(,List,List,List])
return res
print(find(,0))
print("-" * 8)
print(find(,1))
页:
[1]