3SUM（在等于0的列表中查找所有唯一三元组）

Question

我正在研究3SUM问题（来自leetcode），该问题将一个列表作为输入，并在列表中找到所有唯一的三元组，使得a + b + c = 0。我不太确定我的代码在做什么错，但是当前它为此列表返回一个空列表[-1，0，1，2，-1，-4]，因此它无法识别任何总计为0的三元组我将不胜感激任何建议或改进的代码。

这是我的代码：

result = []
nums.sort()
l = 0
r=len(nums)-1
for i in range(len(nums)-2):
    while (l < r):
        sum = nums[i] + nums[l] + nums[r]
        if (sum < 0):
            l = l + 1
        if (sum > 0):
            r = r - 1
        if (sum == 0): 
            result.append([nums[i],nums[l],nums[r]])
print(result)

Answer 1

需要注意的几件事。

1. 请勿将其sum用作变量名，因为这是内置函数。
2. 由于您进行了初始化l = 0并且也i从此处开始，因此索引编制有些问题0。
3. 不要为自己的桂冠而休息：l找到成功的组合时，请增加其值。忘记这一步真的很容易！

下面是您代码的编辑版本。

nums = [-1, 0, 1, 2, -1, -4]
result = []
nums.sort()
r=len(nums)-1
for i in range(len(nums)-2):
    l = i + 1  # we don't want l and i to be the same value.
               # for each value of i, l starts one greater
               # and increments from there.
    while (l < r):
        sum_ = nums[i] + nums[l] + nums[r]
        if (sum_ < 0):
            l = l + 1
        if (sum_ > 0):
            r = r - 1
        if not sum_:  # 0 is False in a boolean context
            result.append([nums[i],nums[l],nums[r]])
            l = l + 1  # increment l when we find a combination that works

>>> result
[[-1, -1, 2], [-1, 0, 1], [-1, 0, 1]]

如果需要，可以从列表中省略重复项。

unique_lst = []
[unique_lst.append(sublst) for sublst in result if not unique_lst.count(sublst)]

>>> unique_lst
[[-1, -1, 2], [-1, 0, 1]]

另一种方法使用itertools.combinations。这不需要排序列表。

from itertools import combinations

result = []
for lst in itertools.combinations(nums, 3):
    if sum(lst) == 0:
        result.append(lst)

嵌套的for循环版本。这种方法不是超级支持者，但基本上是itertools.combinations解决方案的强力版本。由于与上述方法相同，因此无需排序。

result = []
for i in range(0, len(nums)-2):
    for j in range(i + 1, len(nums)-1):
        for k in range(j + 1, len(nums)):
            if not sum([nums[i], nums[j], nums[k]]):  # 0 is False
                result.append([nums[i], nums[j], nums[k]])