力扣 ——4Sum （四数之和）python 实现
2020-12-13 14:22
标签：targe pen target continue list 题目 type for bsp 题目描述： 中文： 给定一个包含 n 个整数的数组 nums 和一个目标值 target，判断 nums 中是否存在四个元素 a，b，c 和 d ，使得 a + b + c + d 的值与 target 相等？找出所有满足条件且不重复的四元组。 英文： Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. 题目来源：力扣题库 力扣 ——4Sum （四数之和）python 实现 标签：targe pen target continue list 题目 type for bsp 原文地址：https://www.cnblogs.com/spp666/p/11559534.htmlclass Solution(object):
def fourSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[List[int]]
"""
nums = sorted(nums)
res = []
if not nums or len(nums) :
return res
if nums[0] + nums[1] + nums[2] + nums[3] > target:
return res
if nums[-1] + nums[-2] + nums[-3] + nums[-4] target:
return res
for i in range(0, len(nums)):
if nums[i] + nums[-1] + nums[-2] + nums[-3] target:
continue
for j in range(i + 1, len(nums) - 2):
if nums[i] + nums[j] + nums[-2] + nums[-1] target:
continue
x = j + 1
y = len(nums) - 1
while x y:
if nums[i] + nums[j] + nums[x] + nums[y] == target:
res.append([nums[i], nums[j], nums[x], nums[y]])
x = x + 1
while x and nums[x] == nums[x - 1]:
x = x + 1
elif nums[i] + nums[j] + nums[x] + nums[y] target:
x = x + 1
else:
y = y - 1
rr = []
for r in res:
if r not in rr:
rr.append(r)
return rr