3SUM(查找列表中等于 0 的所有唯一三元组)

我正在研究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)

有几件事需要注意。

不要使用 sum 作为变量名称，因为这是一个内置函数。
您的索引有点问题，因为您初始化了l = 0并且i也从0开始。
不要固步自封：当你找到一个成功的组合时，增加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.combs。这不需要排序列表。

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

嵌套的循环版本。不是这种方法的忠实粉丝，但它基本上是itertools.combres解决方案的蛮力版本。由于它与上述方法相同，因此不需要排序。

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

取消注释我的解决方案中的打印语句：

class Solution:

    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # print('Input: {}'.format(nums))
        nums.sort() # inplace sorting, using only indexes
        N, result = len(nums), []
        # print('Sorted Input: {}'.format(nums))
        for i in range(N):
            if i > 0 and nums[i] == nums[i-1]:
                # print("Duplicate found(when 'i' iterate ) at index: {}, current: {}, prev: {}, so JUMP this iteration------".format(i,nums[i], nums[i-1]))
                continue
            target = nums[i]*-1
            s,e = i+1, N-1
            # print('~'*50)
            # print("Target: {} at index: {} & s: {}  e: {} {}".format(target,i, s, e, '----'*2))
            while s<e: # for each target squeeze in s & e
                if nums[s]+nums[e] == target:
                    result.append([nums[i], nums[s], nums[e]])
                    # print(' {} + {} == {}, with  s: {} < e: {}, Triplet: {},  MOVING --> R'.format(nums[s], nums[e], target,s, e,result))
                    s = s+1
                    while s<e and nums[s] == nums[s-1]: # duplicate
                        # print("Duplicate found(when 's' iterates) at s: {} < e: {}, WILL KEEP MOVING ---> R  (s: {}) == (s-1: {})".format(s, e, nums[s], nums[s - 1]))
                        s = s+1
                elif nums[s] + nums[e] < target:
                    # print(' {} + {} < {}, with s: {} e: {}, MOVING ---> R'.format(nums[s], nums[e], target,s, e))
                    s = s+1
                else:
                    # print(' {} + {} > {}, with s: {} e: {}, MOVING <--- L'.format(nums[s], nums[e], target,s, e))
                    e = e-1
        return result

它将帮助您更好地理解算法。此外，该算法比上述可用选项快 3 倍。与上述替代方案相比，它需要 ~892.18 毫秒，运行时间为 ~4216.98 毫秒。开销是由于额外删除重复逻辑。

我做了与 3novak 类似的方法，但我在数字列表小于三个整数的情况下添加了返回空列表。

class Solution:
def threeSum(self, nums):
    """
    :type nums: List[int]
    :rtype: List[List[int]]
    """        
    # if less than three numbers, don't bother searching
    if len(nums) < 3:
        return []
    # sort nums and use current sum to see if should have larger number or smaller number
    nums = sorted(nums)
    triplets = []
    for i in range(len(nums)-2):    # i point to first number to sum in list
        j = i + 1                   # j points to middle number to sum in list
        k = len(nums) - 1           # k points to last number to sum in list
        while j < k:
            currSum = nums[i] + nums[j] + nums[k]
            if currSum == 0:
                tmpList = sorted([nums[i], nums[j], nums[k]])
                if tmpList not in triplets:
                    triplets.append(tmpList)
                j += 1 # go to next number to avoid infinite loop
            # sum too large, so move k to smaller number
            elif currSum > 0:
                k -= 1
            # sum too small so move j to larger number
            elif currSum < 0:
                j += 1
    return triplets

我在leetcode上做了同样的问题，但仍然有运行时错误。这也可以通过使用类似二叉搜索树的算法来查找第三个结果来完成。

使用双指针方法：

首先对列表进行排序。
从左到右迭代。假设当前位置为i，将左侧位置设置为i+1，并将右端设置为列表N-1的末尾。
- 如果总和大于 0，则将右端减少 1。
- 否则，如果总和小于 0，则将左端增加 1，
- 否则，请检查新条目的唯一性，如果它是唯一的，请将其添加到答案列表中。继续搜索更多条目 leftEnd++, rightEnd-- .

爪哇代码：

public ArrayList<ArrayList<Integer>> threeSum(ArrayList<Integer> A) {
    ArrayList<ArrayList<Integer>> ans =  new ArrayList<ArrayList<Integer>>();
    Collections.sort(A); // takes O(nlogn)
    if (A.size() < 3) return ans;
    ArrayList<Integer> triplet = new ArrayList<>();
    for(int i = 0; i < A.size()-3; i++){ // takes O(n^2)
        if (i > 0 && A.get(i) == A.get(i-1)) continue; // to maintain unique entries
        int r = A.size()-1;
        int l = i+1;
        while (l < r){
            int s = sumOfThree(A, i, l, r);
            if (s == 0){
                if (ans.size() == 0 || !bTripletExists(A, i, l, r, triplet)){
                    triplet = getNewTriplet(A, i, l, r); // to be matched against next triplet
                    ans.add(triplet);
                }
                l++;
                r--;
            }else if (s > 0){
                r--;
            }else {
                l++;
            }
        }
    }
    return ans;
}
public int sumOfThree(ArrayList<Integer> A, int i, int j, int k){
    return A.get(i)+A.get(j)+A.get(k);
}
public ArrayList<Integer> getNewTriplet(ArrayList<Integer> A, int i, int j, int k){
    ArrayList<Integer> newTriplet = new ArrayList<>();
    newTriplet.add(A.get(i));
    newTriplet.add(A.get(j));
    newTriplet.add(A.get(k));
    return newTriplet;
}
public boolean bTripletExists(ArrayList<Integer> A, int i, int j, int k, ArrayList<Integer> triplet){
    if (A.get(i).equals(triplet.get(0)) && 
        A.get(j).equals(triplet.get(1)) &&
        A.get(k).equals(triplet.get(2)))
        return true;
    return false;
}

上面给出的大多数答案都很棒，但在leetcode上的一些边缘情况失败了。我添加了更多检查以通过所有测试用例

class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
    # if the list has less than 3 elements
    if len(nums)<3:
        return []
    # if nums is just zeroes return just one zeroes pair
    elif sum([i**2 for i in nums]) == 0:
        return [[0,0,0]]
    nums.sort()
    result = []

    for i in range(len(nums)):
        #duplicate skip it
        if i > 0 and nums[i]== nums[i-1]:
            continue
        # left pointer starts next to current i item
        l = i+1
        r = len(nums)-1
        while l< r:
            summ = nums[l] + nums[r]
            # if we find 2 numbers that sums up to -item
            if summ == -nums[i]:
                result.append([nums[i],nums[l],nums[r]])
                l +=1
                # duplicate skip it
                while l<r and nums[l] == nums[l-1]:
                    l +=1

            # if the sum is smaller than 0 we move left pointer forward
            elif summ + nums[i] < 0:
                l +=1
            # if the sum is bigger than 0 move the right pointer backward   
            else:
                r -=1
    return result

相关内容

最新更新

热门标签：