Leetcode15. 三数之和-python

本文主要是介绍Leetcode15. 三数之和-python，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

难度：中等

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

注意：答案中不可以包含重复的三元组。

示例：

给定数组 nums = [-1, 0, 1, 2, -1, -4]，满足要求的三元组集合为：
[[-1, 0, 1],[-1, -1, 2]
]

思路：这个地方也想到一个刚刚做的一个题就是双指针法，不过然后一想，可能需要排序，这里就有个问题...满足要求的三元组是否有顺序要求...简单说 排序后的顺序可能是[-1,0,1],如果不排序的可能是[0,1,-1]，所以先试试...如果不行就找到满足的三元组后再调整顺序。

具体的双指针法如下：

基本规则：

• 如果长度<3，直接返回[]
• 对数组排序，最外层循环也是遍历该数组（i）
• 如果num[i]>0，说明后面也都是正数，不可能凑出来0了，后面也没必要遍历了
• 对于重复元素的num元素需要跳过（可以解决结果数组的重复问题）（可以在排序的时候直接解决重复元素）
• 两个指针的初始值，左指针 L=i+1L=i+1，右指针 R=n−1R=n−1（L<R）

循环过程：

1. 当nums[i]+nums[L]+nums[R]==0nums[i]+nums[L]+nums[R]时，添加元素
2. 若和大于0，说明num[R]太大，R左移
3. 若和小于0，说明num[L]太小，L右移

遇见的坑：重复数据不能...丢弃，否则类似,-1-1,2或者0,0,0这种就查不到了，只能查询过程中避开，而不能直接去掉

错误代码（无法找到含重复数据结果）：

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""n=len(nums)res=[]#特殊情况if n<3:return []#排序nums.sort()num=[]#去重复for i in range(n):if nums[i] not in num:num.append(nums[i])res=[]n=len(num)for i in range(n):if(num[i]>=0):return res#初始化指针L=i+1R=n-1#移动指针while(L<R):if(num[i]+num[L]+num[R]==0):res.append([num[i],num[L],num[R]])L=L+1R=R-1continueelif(num[i]+num[L]+num[R]>0):R=R-1else:L=L+1return res

正确代码：

class Solution(object):def threeSum(self, nums):""":type nums: List[int]:rtype: List[List[int]]"""n=len(nums)res=[]#特殊情况if n<3:return []#排序nums.sort()res=[]for i in range(n):if(nums[i]>0):return res#重复数据不用再次循环if(i>0 and nums[i]==nums[i-1]):continue#初始化指针L=i+1R=n-1while(L<R):if(nums[i]+nums[L]+nums[R]==0):res.append([nums[i],nums[L],nums[R]])#找到结果时，如果重复数据存在，直接略过后继续查找while(L<R and nums[L]==nums[L+1]):L=L+1while(L<R and nums[R]==nums[R-1]):R=R-1L=L+1R=R-1elif(nums[i]+nums[L]+nums[R]>0):R=R-1else:L=L+1return res

 

 

 

 

这篇关于Leetcode15. 三数之和-python的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---