题干
给定一个包含 n 个整数的数组 nums, 判断 nums 中是否存在三个元素 a,b,c , 使得 a + b + c = 0 ? 找出所有满足条件且不重复的三元组.
注意: 答案中不可以包含重复的三元组.
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4],
满足要求的三元组集合为:
- [
- [-1, 0, 1],
- [-1, -1, 2]
- ]
分析
这个题目思路还是比较简单的, 暴力肯定是要 pass, 肯定超时, 所以需要就是尽力的优化时间复杂度. 所有元素肯定都要用到, O(n) 应该就是时间复杂度的极限了. 如何一遍遍历, 找出所有的结果? 先给元素排个序就 OK 了.
代码
- class Solution:
- def threeSum(self, nums: List[int]) -> List[List[int]]:
- nums.sort()
- res =[]
- i = 0
- for i in range(len(nums)):
- if i == 0 or nums[i]>nums[i-1]:
- l = i+1
- r = len(nums)-1
- while l <r:
- s = nums[i] + nums[l] +nums[r]
- if s ==0:
- res.append([nums[i],nums[l],nums[r]])
- l +=1
- r -=1
- while l < r and nums[l] == nums[l-1]:
- l += 1
- while r> l and nums[r] == nums[r+1]:
- r -= 1
- elif s>0:
- r -=1
- else :
- l +=1
- return res
欢迎大家关注我的公众号
半亩房顶
来源: http://www.jianshu.com/p/f8094ad307ee