LeetCode15. 三数之和

题目来源：力扣（LeetCode）

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

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

示例1：

输入：nums = [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]

  

 

  
1
  
2
 

示例2：

输入：nums = []
输出：[]

  

 

  
1
  
2
 

示例3：

输入：nums = [0]
输出：[]

  

 

  
1
  
2
 

提示：

• 0 <= nums.length <= 3000
• -105 <= nums[i] <= 105

解题思路：

• 特殊情况：nums 长度 length 小于 3，返回 []；对排序后 nums，若前三个值 >0 或后三个值 < 0，返回 [] 。

• 对数组进行排序。

• 遍历排序后数组：

1. 若 nums[i] > 0：由于已排序，所以后面不可能有三个数加和等于 0，直接返回结果 rst。
2. 对于重复元素：跳过，避免出现重复解
3. 令左指针 left = i + 1，右指针 right = length - 1，当 L < R 时，执行循环：
   当 nums[i] + nums[left] + nums[right] == 0 ，执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将 L, R 移到下一位置，寻找新的解；若和大于 0，说明 nums[right] 太大，right 左移；若和小于 0，说明 nums[left] 太小，left 右移。

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        length = len(nums)
        if length < 3:
            return []
        # 对nums排序（升序）
        nums.sort()
        if sum(nums[:3]) > 0 or sum(nums[-3:]) < 0:
            return []
        rst = []
        for i in range(length - 2):
            # 第一个数字已经>0，第二、三个数字只会比0大，故之后不存在满足条件的组合
            if nums[i] > 0:
                return rst
            # 跳过重复的组合
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            left = i + 1
            right = length - 1
            while left < right:
                if nums[i] + nums[left] + nums[right] == 0:
                    # 保存结果
                    rst.append([nums[i], nums[left], nums[right]])
                    # 跳过重复的组合
                    while left < right and nums[right] == nums[right - 1]:
                        right -= 1
                    # 跳过重复的组合
                    while left < right and nums[left] == nums[left + 1]:
                        left += 1
                    right -= 1
                    left += 1
                # 三者结果小于0，left（第二个数字）右移（增大）
                elif nums[i] + nums[left] + nums[right] < 0:
                    left += 1
                # 三者结果大于0，right（第三个数字）左移（减小）
                else:
                    right -= 1
        return rst

  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
  
27
  
28
  
29
  
30
  
31
  
32
  
33
  
34
  
35
  
36
  
37
  
38
  
39
  
40
  
41
  
42
 

文章来源: blog.csdn.net，作者：Dream丶Killer，版权归原作者所有，如需转载，请联系作者。

原文链接：blog.csdn.net/qq_43965708/article/details/116836307