三数之和
问题
给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。 注意：答案中不可以包含重复的三元组。LeetCode原题入口
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ]
思路
如果简单采用暴力遍历的方式，时间复杂度为 O(n^3) ，时间上肯定无法通过。可先对数组进行排序，时间复杂度为 O(n\log n) ，接着从数组第一个数开始遍历，在剩下的数中取2数之和，正好等于第一个数的相反数，这样3者之和正好为0。设置第一个指针遍历数组，假设遍历到的当前数为x，则要找的2数之和target=-x，由于数组已经经过排序，后面2数可再用2个指针表示，1个指向第1个数的后一个数，也就是正好大于x的数，另1个指向数组最后一位，也就是最大的那个数。计算2个指针所指向数字之和，如果结果大于target，说明结果偏大，将第2个指针向左移动；如果结果小于target，将第1个指针向右移动，使结果偏大；如果相等，说明符合条件，将数字收纳到结果集里面。最后，由于题目不允许重复，这3个指针如果移动过程中，碰到和上一个数字一样，则直接跳过，时间复杂度为 O(n^2) 。
代码
1234567891011121314151617181920212223 | def threeSum(self, nums: List[int]) -> List[List[int]]: res=[] nums=sorted(nums) for i in range(len(nums)): if i>0 and nums[i]==nums[i-1]: continue target=-nums[i] j,k=i+1,len(nums)-1 while j<k: if nums[j]+nums[k]>target: k-=1 elif nums[j]+nums[k]<target: j+=1 else: if nums[j]+nums[k]==target: res.append([nums[i],nums[j],nums[k]]) j+=1 k-=1 while j<k and nums[j]==nums[j-1]: j+=1 while j<k and nums[k]==nums[k+1]: k-=1 return res |
|---|
腾讯云开发者
