题的问题

y1qcy

给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。
例子：给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums = sorted(nums)
        if len(nums) < 3 or nums[0] > 0 or nums[-1] < 0:
            return []
        
        result = []
        i = 0

        while nums[i] <= 0 and i < len(nums)-1:
            if i > 0 and nums[i] == nums[i-1]:
                i += 1
                continue
            j = i+1
            k = len(nums)-1
            while j<k:    
                if nums[j]+nums[i]+nums[k] > 0:
                    k -= 1
                    # while k > j and nums[k] == nums[k+1]:
                    #     k -= 1
                elif nums[j]+nums[i]+nums[k] < 0:
                    j += 1
                    # while j < k and nums[j]==nums[j-1]:
                    #     j += 1
                else:
                    result.extend([[nums[i],nums[j],nums[k]]])
                    j += 1
                    k -= 1
                    while j<k and nums[k] == nums[k+1]: k-=1
                    while j<k and nums[j] == nums[j-1]: j+=1
            i += 1
        return result

为什么注释的几行去掉后 效率提高了很多呢？
思路是固定最左边 然后右边双指针寻找 跳过重复项

March2615

你注释的部分就是跳过重复项的操作呀

ouyunfu

combinations函数便方便些

nums = [-1, 0, 1, 2, -1, -4]
from itertools import combinations as cb
def threeSum(nums):
    result=[]
    for i in cb(nums,3):
        j=sorted(list(i))
        if sum(j)==0 and j not in result:
            result.append(j)
    return result

何佳鑫

不会