[数据结构与算法]【leetcode】15. 三数之和

?? 问题描述：给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。

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

解题思路：

• 首先将无序的数组变成有序数组
• 取出数组中的一个值nums[i]，取出顺序按照下标0~len(nums)
• 然后剩下的数组利用left和right指针遍历，total = i + left + right ,如果total>0，right向左移动，total<0，left向右移动。
• 如果total = 0，则保存i,left,right所对应的数值，因为题目中说了答案中不可以包含重复的三元组，所以需要再判断一下right== right -1 和left == left + 1，如果true的话，left向右移动，right向左移动，直到等于false
• 保存left，right的值后，就找到了一个符合三元组的解，此时将left 和right分别向右和向左移动，直到找到所有的解。

代码如下（python）：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        ans = []
        n = len(nums)
        nums.sort()
        for i in range(n):
            left = i + 1
            right = n - 1
            if nums[i] > 0:
                break

            if i >= 1 and nums[i] == nums[i-1]:  # 固定num1的值相同，没必要寻找第二次
                continue

            while left < right:  # 固定num1后 利用左右指针去找三数之和为0
                total = nums[i] + nums[left] + nums[right]

                if total > 0:# 因为是有序的
                    right -= 1  
                elif total < 0 :
                    left += 1
                
                else:# 找到了三数之和为0
                    ans.append([nums[i],nums[left],nums[right]])
                    #答案中不可以包含重复的三元组：nums[left]==nums[left + 1]
                    while left != right and nums[left]==nums[left + 1]: 
                        left += 1
                    while left != right and nums[right] == nums[right - 1]:
                        right -= 1
                    

                    #不断缩小两边界，直到找到num[i] + left + right =0的所有三元组
                    left += 1
                    right -= 1
        return ans