LeetCode-15 三数之和

题目：三数之和

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

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

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

思路

之前曾有两数之和的题目，这次其实可以先把给定数组进行排序之和，依次取0到len(nums)-2的数当做第一个数，然后计算剩下的数组的两数之和是否加上第一个数为0即可。

使用sort()方法进行排序，如果长度小于3直接返回空
依次取i为第0到len(nums)-2个数作为第一个数num1
- 为了防止重复，如果i不是0的情况下，当前num1与上一轮的num1相同则跳过
- 依次取j从i+1开始到len(nums)-1个数做为第二个数num2
  - 如果当前j不等于i+1的情况下，当前num2与上一轮的num2相同则跳过
  - 判断num3=-(num1+num2)是否在剩余数组中，存在则加入到输出

实现：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        out = []
        nums.sort()
        if len(nums) < 3:
            return []
        for i in range(0, len(nums) -2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            num1 = nums[i]
            for j in range(i + 1, len(nums) - 1):
                num2 = nums[j]
                if j > i + 1 and num2 == nums[j - 1]:
                    continue
                num3 = -(num1 + num2)
                if num3 in nums[j + 1:]:
                    temp_out = [num1, num2, num3]
                    out.append(temp_out)
        return out

优化方法

上述方法嵌套了两次层循环，且第二层循环需完全遍历剩余数组。可以使用双指针的方式前后同时移动来提升效率。

使用sort()方法进行排序，如果长度小于3直接返回空
依次取i为第0到len(nums)-2个数作为第一个数num1
- 为了防止重复，如果i不是0的情况下，当前num1与上一轮的num1相同则跳过
- 初始化第2个数的index为l，第三个数的index为r=len(nums)-1
- 在确保l<r的情况下开始移动
  - 如果当前三个数相加为0：记录当前组合后，l向后移动，r向前移动
    - 如果移动后的l,r值与上一值相等则继续移动
  - 如果当前三个数相加大于0：r向左移动
  - 如果当前三个数相加小于0：l向右移动

实现：

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        out = []
        nums.sort()
        if len(nums) < 3:
            return []
        for i in range(0, len(nums) -2):
            if i > 0 and nums[i] == nums[i - 1]:
                continue
            num1 = nums[i]
            l = i + 1
            r = len(nums) - 1
            while l < r:
                temp_sum = nums[l] + nums[r] + num1
                if temp_sum == 0:
                    temp_out = [num1, nums[l], nums[r]]
                    out.append(temp_out)
                    l += 1
                    r -= 1
                    while l < r and nums[l] == nums[l - 1]:
                        l += 1
                    while l < r and nums[r] == nums[r + 1]:
                        r -= 1
                elif temp_sum > 0:
                    r -= 1
                else:
                    l += 1
        return out

如果大家有更好的方法，欢迎一起探讨。

题目： 三数之和

思路

优化方法

题目：三数之和