三和算法解决方案 [英] Three sum algorithm solution

问题描述

原始问题陈述：

给出一个包含n个整数的数组S，S中是否存在元素a，b，c使得a + b + c = 0？在数组中找到所有零的三元组，它们的总和为零。

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

注意：解决方案集不得包含重复的三元组。

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is: [[-1, 0, 1], [-1, -1, 2]]

您好，我很久以前就解决了LeetCode上的两个和问题，并且考虑过也可以使用它来解决三个和。我的想法是，对于每个元素，在其余列表中找到两个元素，这些元素的总和为* * -1，得到0。但是，此代码未通过所有测试，例如

Hello I solved the Two Sum problem on LeetCode some time back and I thought of using it to solve the three sum as well. My idea is that for every element find two elements in the remaining list which sum up to element * -1 to get 0. However, this code doesn't pass all the test, for example

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

我真的不知道怎么了。有人能对我解释这个问题吗？
谢谢

I don't really know what's wrong. Can someone be kind enough to explain the problem to me. Thank you

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/

The one I'm using to solve this: 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]]

这篇关于三和算法解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！