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