LC14三数之和

给定一个包含n个证书的数组nums，判断nums中是否存在3个元素a, b, c，使得a+b+c=0？找出所有满足条件且不重复的三元组。

我的解法

• 暴力搜索，将数据集分为自然数、零和负数三个列表
• 如果零集合中的元素大于3个，则在返回结果中增加3个0的选项
• 从自然数集合和负数集合各取一个数，求和的相反数，在两个列表中查找是否存在该元素
• 如果存在并且和集合中的元素不重复，加入到结果中，并加入到要比较的集合中

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 生成自然数、负数和零3个列表
        pos = [x for x in nums if x >= 0]
        zeros = [x for x in nums if x == 0]
        neg = [x for x in nums if x < 0]

        result = []
        dump = []

        if len(zeros) >= 3:
            result.append([0,0,0])

        for i in range(len(pos)):
            for j in range(len(neg)):
                sub = - (pos[i] + neg[j])
                if (sub in pos and pos.index(sub) != i) or (sub in neg and neg.index(sub) != j):
                    res = [pos[i], neg[j], sub]
                    if set(res) not in dump:
                        result.append(res)
                        dump.append(set(res))

        return result

• 这种解法会超时

---

官方解答Python版

• 将数组排序
• 定义3个指针i, j, k
• 遍历i
• 该问题转化为在i之后的数组中寻找nums[j] + nums[k] = -nums[i]，可以将3数之和转化为两数之和，使用双指针的方法

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        # 先对列表排序
        nums.sort()
        res =[]
        # 遍历列表中的每一个元素
        for i in range(len(nums)):
            # 如果是首元素或者该元素大于前一个元素
            # 为了防止出现多个元素重复，导致结果重复的现象
            if i == 0 or nums[i]>nums[i-1]:
                l = i+1
                r = len(nums)-1
                # 当左侧指针位置小于右侧指针位置
                while l < r:
                    s = nums[i] + nums[l] +nums[r]
                    if s ==0:
                        res.append([nums[i],nums[l],nums[r]])
                        l +=1
                        r -=1
                        # 防止结果重复，跳过重复的元素
                        while l < r and nums[l] == nums[l-1]:
                            l += 1
                        while r > l and nums[r] == nums[r+1]:
                            r -= 1
                    elif s>0:
                        r -=1
                    else :
                        l +=1
        return res

赏

~~感谢款待~~

支付宝

微信