Python第17题:三数之和【已优化，完美续集】【leetcode】

原始编程试题如下：

给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。

注意：答案中不可以包含重复的三元组。

第一次编写链接如下：
https://www.toutiao.com/article/7484270109578560027/

第二次编写链接如下：
https://www.toutiao.com/article/7484802365191684646/

经过再三思考，发现了第二次编码中影响效率的地方：

1. 重复结果检查效率低：使用了 if result not in resultList 来检查结果是否已经存在，这种方法的时间复杂度是 O(n)，对于较大的数据集来说效率很低。
2. 频繁的列表操作：每次找到一个三元组时，都会创建一个新的列表 result，并将其添加到 resultList 中，这会增加额外的开销。

问题点找到了，解决的办法其实就很简单了，于是，在第二次的基础上，写出了最终的代码：

可编辑代码如下：

class Solution:
    def threeSum(self, nums: list[int]) -> list[list[int]]:
        resultList = []
        numlen = len(nums)
        nums.sort()
        for i in range(0, numlen-2):
            start, end = i+1, numlen-1
            # 跳过重复的数
            if (i > 0 and nums[i] == nums[i - 1]) :
                continue
            # 优化点1：提前终止条件
            if nums[i] + nums[i + 1] + nums[i + 2] > 0:
                break
            if nums[i] + nums[numlen - 2] + nums[numlen - 1] < 0:
                continue
            while(start < end):
                if (nums[i] + nums[start]+ nums[end] == 0):
                    # 优化点2：直接将list加入到返回列表中
                    resultList.append([nums[i], nums[start], nums[end]])
                    start += 1
                    end -= 1
                    while (start < end) and nums[start] == nums[start-1]:
                        start += 1
                    while (start < end) and nums[end] == nums[end+1]:
                        end -= 1    
                elif (nums[i] + nums[start] + nums[end] > 0):
                    end -= 1
                else:
                    start += 1
        return resultList

执行结果如下：