leetcode--三数之和（python实现双指针法）

矫情吗；* 2022-12-17 05:20 124阅读 0赞

## 题目描述： ##

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

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

## 例子： ##

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

思路分析：本题目与之前的[两数之和][Link 1]相似，但是如果用暴力解决的办法，时间复杂度为O(N^3)而且在leetcode中容易超时，因此本题采用双指针法。

首先先排除一下特例的情况如数组的元素长度小于3或者空数组，在接着对数组进行排序，如果最小的元素都大于0，不存在三数之和为0。我们将左指针设为i+1，右指针len(nums)-1，如果存在三数之和为0，则左右指针各向右移动,接着需要判断该数的附近是否有重复，进行去重，各自指针进行移动。如果三数之和大于0，右指针左移，左指针右移。

## 代码展示 ##

class Solution(object):
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: List[List[int]]
            """
            #双指针法
            n=len(nums)
            ans=[]
            if n<3 or nums==None:
                return []
            ans=[]
            nums.sort()
            for i in range(n):
                if nums[i]>0:
                    return ans
                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:
                        ans.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 ans

[Link 1]: https://blog.csdn.net/kingJamesbond/article/details/107856176?ops_request_misc=%257B%2522request%255Fid%2522%253A%2522160329264619195264762256%2522%252C%2522scm%2522%253A%252220140713.130102334.pc%255Fblog.%2522%257D&request_id=160329264619195264762256&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~blog~first_rank_v1~rank_blog_v1-10-107856176.pc_v1_rank_blog_v1&utm_term=%E4%B8%A4%E6%95%B0%E4%B9%8B%E5%92%8C&spm=1018.2118.3001.4187