题目：

题目链接： https://leetcode-cn.com/problems/3sum/

 

解题思路：

双指针

先对数组进行排序(快排)，然后开始遍历

先固定最左边的一个数字，假设下标为index

对固定数字的右半部分，使用双指针遍历，开始时的left= index + 1, right= len(nums) - 1

当前的三数之和sum = nums[index] + nums[left] + nums[right]，然后进行如下判断：

1. 如果nums[index] > 0，则left和right如何移动，都无法使三数之和为0，直接退出所有循环
2. 如果sum > 0 并且 nums[left] > 0，则表示当前固定的index，和剩余数字组合成的三数之和，都大于0，进行下一次循环，index = index + 1
3. 如果left = right，进行下一次循环，index = index + 1
4. 如果sum = 0，记录当前的三个数字，并进行下记操作
   1. 向右移动left，直到nums[left] != nums[left - 1]
   2. 向左移动right，直到nums[right] != nums[right + 1]
5. 如果sum > 0，向左移动right
6. 如果sum < 0，向右移动left

 

代码实现：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums_len = len(nums)
        if nums_len < 3:
            return []
        
        res = []
        nums.sort()
        if nums[0] > 0 or nums[-1] < 0:
            return []
        
        index = 0
        for index in range(0, nums_len):
            if nums[index] > 0:
                break
            elif index > 0 and nums[index] == nums[index - 1]:
                continue
                
            left, right = index + 1, nums_len - 1
            while left < right:
                curr_sum = nums[index] + nums[left] + nums[right]
                if curr_sum == 0:
                    res.append([nums[index], nums[left], nums[right]])
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                        
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    left += 1
                    right -= 1
                elif curr_sum > 0:
                    right -= 1
                else:
                    left += 1
                
        return res