欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Leetcode 15.三数之和题解

程序员文章站 2022-07-14 17:34:09
...

Leetcode 15.三数之和题解

题目链接:

https://leetcode-cn.com/problems/3sum/

题目描述

给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。

思路

看到这道题我的第一反应就是暴力解,遍历三遍数组求解,这样做显然是O(n3)的时间复杂度。于是我就开始想有没有更快的解法,很容易就可以想到先固定一个数,然后去求数组中和为这个数负数的另两个数。咦,仔细一看那这不就是leetcode第一题嘛。只要做过应该就知道可以拿hash来求解,那直接把这个方法套过来可以吗?答案显然是可以的。不过还需要注意的是答案中不包含重复三元组,所以最好先对数组排个序。那么这个方法的时间复杂度就是O(2),空间复杂度就是O(n)。
u1s1,我的思路到这里就停止了,但看了一眼答案,发现用双指针的方法可以做到空间复杂度只有O(1)。我觉得很强,所以也在这里分享一下。双指针法有一个前提是数组需要有序,这是因为有序数组才可以决定两个指针的移动顺序和方向。假设我们是一个升序排列的数组,如下图,我们先遍历我们的数组,固定三元组的其中一位(就好比图中的3),然后设定两个指针分别是其下一位和数组末尾(图中红色箭头)。
Leetcode 15.三数之和题解
当两个指针对应的数求和结果大于固定元的负数时,那么向左移动右侧指针,如果小于,则向右移动左侧指针,如果相等,那么便是其中一个答案,并同时向内侧移动两个指针。

代码

hash法

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        num_dict = {}
        for n in nums:
            if n in num_dict:
                num_dict[n] += 1
            else:
                num_dict[n] = 1
        for i, n in enumerate(nums):
            if i > 0 and nums[i-1] == n:
                continue
            for j in range(i+1, len(nums)):
                if j > i+1 and nums[j-1] == nums[j]:
                    continue
                if -nums[j]-n not in num_dict:
                    continue
                if -nums[j]-n < nums[j]:
                    continue
                if -nums[j]-n > nums[j]:
                    res.append([n, nums[j], -nums[j]-n])
                else:
                    tmp = 2 if n != nums[j] else 3
                    if num_dict[-nums[j]-n] >= tmp:
                         res.append([n, nums[j], -nums[j]-n])
        return res

双指针法

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        nums.sort()
        res = []
        for i, n in enumerate(nums):
            start, end = i+1, len(nums) - 1
            if i > 0 and nums[i-1] == n:
                continue
            while start < end:
                if nums[start] + nums[end] < -n:
                    start += 1    
                elif nums[start] + nums[end] > -n:
                    end -= 1   
                else:
                    res.append([n, nums[start], nums[end]])
                    start += 1
                    end -= 1
                    while start > i+1 and start < end and nums[start] == nums[start-1]:
                        start += 1
                    while end < len(nums)-1 and end > start and nums[end] == nums[end+1]:
                        end -= 1    
        return res