注意:答案中不可以包含重复的三元组。
思路:1、 将列表从小到大排序。
2、 三个指针i,k,j,i放在最外面(每次循环的第一个,用来计算 nums[i]+nums[k]+nums[j]的值是否为0)。每次进循环k是i后面一个。j每次进循环都是最后一个
3、 每次计算s = nums[i]+nums[k]+nums[j]。如果s==0,append到列表;如果s<0,k指针往右移,并且一直移动到与前一个不相等的(减少重复增加效率);如果s>0,j指针往左移,并且一直移动到与前一个不相等的 def threeSum(nums): savelst = [] nums.sort() for i in range(len(nums)): #第一个数一定要是小于等于0,如果大于零三个数的和不可能等于0 if (i==0 or nums[i]!=nums[i-1])and(nums[i]<=0): k = i+1 j = len(nums)-1#ikj都是下标 while k<j: if nums[i]==nums[k]==nums[j]==0: savelst.append([0,0,0]) break s = nums[i]+nums[k]+nums[j] if s==0: savelst.append([nums[i],nums[k],nums[j]]) k+=1 while nums[k]==nums[k-1]and(k+1<len(nums)-1): k+=1 #j减到与之不相等的数 j-=1 while nums[j]==nums[j+1]: j-=1 elif s>0: j-=1 while nums[j]==nums[j+1]: j-=1 else: k+=1 while nums[k]==nums[k-1]and(k+1<len(nums)-1): k+=1 return savelstprint(threeSum([-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0]))
附上我的答案