LeetCode15 三数之和 - “贪心+双指针: 基于”两数之和“的拓展题“

Leetcode 15： 三数之和

题目链接

发布在LeetCode上的题解

思路

这道题的思路建立在 167.两数之和 的基础上。先来看看”两数之和“的大概题意：

• 已知一个非递减的数组，找出满足相加之和等于目标数 target 的两个数，假设每个输入只对应唯一的答案，而且不可以重复使用相同的元素。

大致思路如下：

• 已知数组是非递减的，采用双指针+贪心的方法，首先初始化左指针 l 和右指针 r ，每次判断 numbers[l] + numbers[r] 和 target 的大小关系，如果大于，说明右指针的值大了，则 r-- ；如果小于，说明左指针的值小了，则 l++ ；如果相等，直接 return （因为题干假设有唯一解）

注：l 只能右移，r 只能左移。

”两数之和“的代码如下：

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers)-1
        while l < r:
            if numbers[l] + numbers[r] < target:
                l += 1
            elif numbers[l] + numbers[r] > target:
                r -= 1
            else:
                return [l+1, r+1]

理解两数之和的思路之后，三数之和就很好处理了。同样地，我们先将原数组排序，方便后续处理可能存在的重复。同时注意到两数之和用到了一个target 变量，这正好可以用于三数之和的第三个数。

解题过程

1. 原数组调用 sort() 函数，确保原数组不递减。
2. 用 i 遍历 nums 数组，nums[i] 作为三个数的第一个数，同时相当于”两数之和“中的 target 变量。
3. 定义左指针 l=i+1 ，右指针 r=len(nums)-1 ，在这个区间寻找第二、三个数。然后采用和”两数之和“中同样的贪心方法。
4. 循环到 nums[l]+nums[r]==-nums[i] 时，将这三个数加入 ans 列表。然后收回之前排序的伏笔——跳过重复项。对于第一个数，注意题干要求三个数各不相同，从第1项开始，i 和 i-1 比较是否相等，若相等则 continue；对于第二三个数字，使用 while 循环过滤重复项，首先需要保证 l<r ，然后将l 项和 l+1 项比较是否相等，r 项和 r-1 项比较是否相等，退出 while 循环后， nums[l]!=nums[l+1] ,nums[r]!=nums[r-1] ，因此还需要 l++, r-- 来获取新的数。
5. 最后返回 ans 列表。

复杂度

时间复杂度：$O(n^2)$

空间复杂度：$O(1)$

Code

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