15. 三数之和

引流：五点钟科技-CSDN博客

题目：

给你一个整数数组?nums?，判断是否存在三元组?[nums[i], nums[j], nums[k]]?满足?i != j、i != k?且?j != k?，同时还满足?nums[i] + nums[j] + nums[k] == 0?。请

你返回所有和为?0?且不重复的三元组。

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

【解题思路】

本题为中等难度的题，但事实上，对题目本身的理解并不难，难得是细节，否则本题完全可以是简单题。注意，类似这种两数之和，三数之和，四数之和的题目，一定优先考虑多指针的解法，例如本题，要求三数之和，那么就考虑用三指针来解，顺其自然，但本题需要注意，人家要求结果中不能有重复答案，这就让我们在遍历数组的时候，要跳过已经遍历过的数字。

我们设计三个指针，初始分别指向数组第一个数、第一个指针的下一个数、最后一个数。既然是顺序遍历，那么我们需要先对数组排个序，这里用升序排列，每次循环让第一个指针保持不动，后面两个指针向内运动，因为是升序，所以当三个指针所指向的数之和小于0，说明第二个指针需要再往大的数指（向右移动），反之，说明第三个指针需要减小指向的数（向左移动），如果三个数相加为0，满足答案要求，记录，且第二、第三个指针同时向内移动一步。注意细节：当第一个指针当前指向的数与上一步指向的数相同，则无需再计算了，继续continue到下一个数，第二个指针、第三个指针都是如此，这样就保证了我们所记录的答案不会重复。

【代码】

    def threeSum(self, nums: List[int]) -> List[List[int]]:
        if len(nums) == 3:
            if sum(nums) == 0:
                return [nums]
            else:
                return []
        nums.sort()
        n = len(nums) - 1
        res = []
        for cur in range(n-1):
            if cur and nums[cur] == nums[cur-1]:
                continue
            left = cur + 1
            right = n
            while left < right:
                if left-1 > cur and nums[left] == nums[left-1]:
                    left += 1
                    continue
                if right+1 < n and nums[right] == nums[right+1]:
                    right -= 1
                    continue
                if nums[cur] + nums[left] + nums[right] == 0:
                    res.append([nums[cur], nums[left], nums[right]])
                    left += 1
                    right -= 1
                elif nums[cur] + nums[left] + nums[right] < 0:
                    left += 1
                else:
                    right -= 1
        return res