leetcode 15. 三数之和

深碍√TFBOYSˉ_ 2022-05-14 07:51 166阅读 0赞

**【前言】**

python刷leetcode题解答目录索引：[https://blog.csdn.net/weixin\_40449300/article/details/89470836][https_blog.csdn.net_weixin_40449300_article_details_89470836]

github链接：[https://github.com/Teingi/test][https_github.com_Teingi_test]

**【正文】**

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

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

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

解法：对数组先进行排序处理，一头一尾设置两个指针，注意去重

class Solution:
        def threeSum(self, nums):
            """
            :type nums: List[int]
            :rtype: 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

[https_blog.csdn.net_weixin_40449300_article_details_89470836]: https://blog.csdn.net/weixin_40449300/article/details/89470836
[https_github.com_Teingi_test]: https://github.com/Teingi/test