原始问题陈述:
给定一个包含 n 个整数的数组 S,S 中是否存在满足 a + b + c = 0 的元素 a、b、C?找到数组中所有唯一的三元组,其总和为零。
注意:解决方案集不得包含重复的三元组。
For example, given array S = [-1, 0, 1, 2, -1, -4],
A solution set is: [[-1, 0, 1], [-1, -1, 2]]
前段时间我在 LeetCode 上解决了二和问题,我想用它来解决三和问题。我的想法是,对于每个元素,在剩余列表中找到两个元素,它们总和为 element * -1 得到 0。但是,这段代码并没有通过所有测试,例如
Input: [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
Output: [[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2]]
Expected: [[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]]
我真的不知道怎么回事。有人可以向我解释一下这个问题吗。
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
def twoSum(self, nums, target):
targ = target
for index, i in enumerate(nums):
targ -= i
if targ in nums[index+1:]:
return [nums[index], nums[nums[index+1:].index(targ)+index+1]]
else:
targ = target
return None
res = []
for index, i in enumerate(nums):
target = i * -1
num = nums[:index] + nums [index+1:]
ans = twoSum(self, num, target)
if ans != None:
temp = ans + [i]
temp.sort()
res.append(temp)
print(res)
import itertools
res.sort()
res = list(res for res,_ in itertools.groupby(res))
return res
原始问题:https://leetcode.com/problems/3sum/description/
我用来解决这个问题的是:https://leetcode.com/problems/two-sum/description/
最佳答案
使用 itertools
。
import itertools
stuff = [-1, 0, 1, 2, -1, -4]
stuff.sort()
ls = []
for subset in itertools.combinations(stuff, 3):
if sum(list(subset))==0:
# first I have sorted the list because of grouping
# Ex: [-1, 0, 1] and [0, 1, -1] are build with the same element
# so here is avoiding this.
if list(subset) not in ls:
ls.append(list(subset))
print(ls)
输入/输出
input : [-1, 0, 1, 2, -1, -4]
output : [[-1, -1, 2], [-1, 0, 1]]
input : [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
output: [[-4, -2, 6], [-4, 0, 4], [-4, 1, 3], [-4, 2, 2], [-2, -2, 4], [-2, 0, 2]]
关于python - 三和算法解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/46066652/