三数之和题目来源：https://leetcode-cn.com/problems/3sum题目给定一个包含n个整数的数组nums，判断nums中是否存在三个元素a,b,c这样a+b+c=0？找出所有满足条件且不重复的三元组。注意：答案中不允许出现重复的三胞胎。示例：给定数组nums=[-1,0,1,2,-1,-4]，满足要求的三元组集合为：[[-1,0,1],[-1,-1,2]]解题思路数组排序+双指针；先提取特例，直接处理。当数组nums为空（或None）或nums长度小于3时，直接返回空列表；排除特殊情况后，先对数组进行排序；遍历数组，判断三个数之和是否为0：先固定一个值，即nums[i]；如果nums[i]大于0，因为数组已经排序，说明nums[i]和后面任意两个值之和不能等于0，直接跳出循环；对值进行去重，避免结果重复，重复的条件是当前值等于前一个值，即nums[i]==nums[i-1]，满足条件直接跳过；定义左右指针L和R，并固定nums[i]的值，当L小于R时，在两个指针的范围内找到与nums[i]之和为0的两个值；当three_num==0时，将三个值添加到返回列表中，继续查找条件的数值。如果nums[L]==nums[L+1]，则表示重复跳过，即让L+=1向右移动；如果nums[R]==nums[R-1]，也表示重复跳过，即让R-=1向左移动；当three_num<0时，表示左指针值太小，左指针向右移动；当three_num>0时，表示右指针的值太大，右指针向左移动。时间复杂度：$O(n^2)$。数组排序：$O(nlogn)$；固定nums[i]值：$O(n)$；双指针遍历：$O(n)$；最终时间复杂度：$O(n)*O(n)+O(nlogn)$，实现类Solutionfor$O(n^2)$图形代码：defthreeSum(self,nums:List[int])->List[List[int]]:'''returnthreeArgs:nums:integerarrayReturns:returntripletset,excludedrepeatedtriplets'''#初始化返回数组res=[]nums_len=len(nums)#特殊情况下，直接返回一个空列表#当nums为空，长度小于3时，如果不是nums或者nums_len<3:returnres#先对数组排序nums.sort()foriinrange(nums_len):#值表对应i固定值#因为数组已经排序，如果nums[i]>0，这个值和后面的值之和必须大于0，如果nums[i]>0直接跳出循环：break#ifnums[i]==nums[i-1]表示已经重复了#跳到重复值的最后1位，以免在返回列表中加入重复的三元组ifi>0andnums[i]==nums[i-1]:continue#左右指针，一个在f之后固定值，另一个是最终值L=i+1R=nums_len-1whileL
