在列表中迭代多个变量而不重复计算？

Question

我正在研究一个程序的一部分，我正在尝试输入一个数字列表并返回所有3个数字组，总和为0，而不是对每个数字进行双重或三重计数。这是我要去的地方：

def threeSumZero2(array):
    sums = []
    apnd=[sorted([x,y,z]) for x in array for y in array for z in array if x+y+z==0]
    for sets in apnd:
        if sets not in sums:
            sums.append(sets)
    return sums

是否有任何代码可以放在第三行，以确保我不会返回[0,0,0]作为答案。

这是我的测试清单：

[-1,0,1,2,-1,4] 

谢谢

*编辑：我应该澄清重复的输入值：此测试列表的预期结果是：

[[-1,-1,2],[-1,0,1]]

Answer 1

你需要组合而不需要替换，这是由itertools提供的。然后你的sums可以被设置为删除有关订购的重复项。

from itertools import combinations

def threeSumZero2(array):
    sums = set()
    for comb in combinations(array, 3):
        if sum(comb) == 0:
            sums.add(tuple(sorted(comb)))
    return sums

print(threeSumZero2([-1,0,1,2,-1,4]))

产量

{(-1, -1, 2), (-1, 0, 1)}

也可以使用集合理解更简洁地编写此解决方案。

def threeSumZero2(nums):
    return {tuple(sorted(comb)) for comb in combinations(nums, 3) if sum(comb) == 0}

More efficient algorithm

虽然，上述算法需要遍历三个项目的所有组合，这使得它成为O（n3）。

用于这种n和问题的一般策略是遍历n-1个组合并散列它们的和，允许根据列表中的数字有效地测试它们。

算法复杂度下降一个数量级，使其成为O（n2）

from itertools import combinations

def threeSumZero2(nums, r=3):
    two_sums = {}
    for (i_x, x), (i_y, y) in combinations(enumerate(nums), r - 1):
        two_sums.setdefault(x + y, []).append((i_x, i_y))

    sums = set()
    for i, n in enumerate(nums):
        if -n in two_sums:
            sums |= {tuple(sorted([nums[idx[0]], nums[idx[1]], n]))
                     for idx in two_sums[-n] if i not in idx}

    return sums

print(threeSumZero2([-1,0,1,2,-1,4]))

产量

{(-1, -1, 2), (-1, 0, 1)}

Answer 2

您可以使用itertools执行此操作（请参阅Oliver的答案），但您也可以使用三个嵌套for循环来实现结果：

def threeSumZero2(lst):
    groups = []
    for i in range(len(lst)-2):
        for j in range(i + 1, len(lst)-1):
            for k in range(j + 1, len(lst)):
                if lst[i] + lst[j] + lst[k] == 0:
                    groups.append((lst[i], lst[j], lst[k]))
    return groups

和你的测试：

>>> threeSumZero2([-1, 0, 1, 2, -1, 4])
[(-1, 0, 1), (-1, 2, -1), (0, 1, -1)]

---

哦，还有list！= array！