LeetCode--015--三数之和(python)

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

先对nums进行排序，再用双指针，L=i+1,R=len(nums)-1，i从索引0开始遍历，until nums[i]>0退出

 1 class Solution:
 2     def threeSum(self, nums: List[int]) -> List[List[int]]:
 3         if(not nums or len(nums)<3):
 4             return []
 5         nums.sort()
 6         res = []
 7         for i in range(len(nums)):
 8             L = i+1
 9             R = len(nums)-1
10             if nums[i]>0:
11                 return res
12             if i > 0 and nums[i-1]==nums[i]:
13                 continue
14             while L <R:
15                 if nums[i]+nums[L]+nums[R]==0:
16                     res.append([nums[i],nums[L],nums[R]])
17                     while L < R and nums[L]==nums[L+1]:
18                         L+=1
19                     while L <R and nums[R]==nums[R-1]:
20                         R-=1
21                     L+=1
22                     R-=1
23                 elif nums[i]+nums[L]+nums[R]>0:
24                     R-=1
25                 else:
26                     L+=1
27         return res
28

时间复杂度：O(N^2) = 数组排序O(NlogN)+遍历数组O(N)*双指针遍历O(N)

空间复杂度：O(1)