算法之美

三数之和–LK

一.题目描述

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

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

示例:

二.思路

  1. 将数组升序排序;
  2. 每次指定一个数字i,剩余两个通过两个指针来寻找,left,right。left首先指定i的下一位,right首先指定最后一个元素。
  3. 如果遍历到的元素大于0,那么代表在以后的寻找中都没有符合条件的组合了,直接返回当前的res结果数组。
  4. 如果 nums[i]+nums[left]+nums[right] 大于0,right指针向前移动一位。
    如果 nums[i]+nums[left]+nums[right] 小于0,left指针向后移动一位。
  5. 如果 nums[i]+nums[left]+nums[right] 等于0,那么res数组添加进三位数字,并且依次判断left的下一位数字是否和left指向的数字相等,right的上一位是否和right指向的数字相等。如果相等那么跳过那些数字。(题里要求结果中不可以有重复的三元组)。
  6. 输出res。

三.python代码

class Solution:
    def threeSum(self, nums):
        
        n=len(nums)
        res=[]
        if(not nums or 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+1
            R=n-1
            while(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+1
                    while(L<R and nums[R]==nums[R-1]):
                        R=R-1
                    L=L+1
                    R=R-1
                elif(nums[i]+nums[L]+nums[R]>0):
                    R=R-1
                else:
                    L=L+1
        return res
nums = [-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
print(Solution().threeSum(nums))

三数之和–LK已关闭评论