题的问题

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
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1. class Solution:
   
2.     def threeSum(self, nums: List[int]) -> List[List[int]]:
   
3.         nums = sorted(nums)
   
4.         if len(nums) < 3 or nums[0] > 0 or nums[-1] < 0:
   
5.             return []
   
6.         
   
7.         result = []
   
8.         i = 0
   
9. 
   
10.         while nums[i] <= 0 and i < len(nums)-1:
    
11.             if i > 0 and nums[i] == nums[i-1]:
    
12.                 i += 1
    
13.                 continue
    
14.             j = i+1
    
15.             k = len(nums)-1
    
16.             while j<k:   
    
17.                 if nums[j]+nums[i]+nums[k] > 0:
    
18.                     k -= 1
    
19.                     # while k > j and nums[k] == nums[k+1]:
    
20.                     #     k -= 1
    
21.                 elif nums[j]+nums[i]+nums[k] < 0:
    
22.                     j += 1
    
23.                     # while j < k and nums[j]==nums[j-1]:
    
24.                     #     j += 1
    
25.                 else:
    
26.                     result.extend([[nums[i],nums[j],nums[k]]])
    
27.                     j += 1
    
28.                     k -= 1
    
29.                     while j<k and nums[k] == nums[k+1]: k-=1
    
30.                     while j<k and nums[j] == nums[j-1]: j+=1
    
31.             i += 1
    
32.         return result

复制代码

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

March2615

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

ouyunfu

combinations函数便方便些

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

复制代码

何佳鑫

不会