leetcodeday15 —三数之和

给你一个包含 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]]

示例 2:

输入:nums = []
输出:[]

示例 3:

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

提示:

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

思路双指针方法:依次对每个元素进行如下判断:-s[i]==s[j]+s[m],其中 s[j]+s[m] 要遍历剩下的元素(采用双指针)


# @lc code=start
class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
            if set(nums)=={0} and len(nums)>=3:
                return [[0,0,0]]
                   
            sets=set()
            lens=len(nums)
            nums =sorted(nums)
            result=[]
            for i in range(lens):
                newlist=nums[0:i]+nums[i+1:]
                
                m=0
                j=lens-1-1
                if nums[i] in sets:
                    continue
                else:
                    sets.add(nums[i])
                while m<j:
                    if newlist[m]+newlist[j]==-nums[i] and sorted([newlist[m],newlist[j],nums[i]])not  in result:
            
                        result.append(sorted([newlist[m],newlist[j],nums[i]]))
                        m=m+1
                    elif newlist[m]+newlist[j]>-nums[i]:
                        j=j-1
                    else:
                        m=m+1
            return result

# @lc code=end

就差超时了……

方法一:排序 + 双指针
题目中要求找到所有「不重复」且和为 0 的三元组,这个「不重复」的要求使得我们无法简单地使用三重循环枚举所有的三元组。这是因为在最坏的情况下,数组中的元素全部为 0,即

[0, 0, 0, 0, 0, …, 0, 0, 0]
任意一个三元组的和都为 00。如果我们直接使用三重循环枚举三元组,会得到 O(N^3)个满足题目要求的三元组(其中 N是数组的长度)时间复杂度至少为 O(N^3)。在这之后,我们还需要使用哈希表进行去重操作,得到不包含重复三元组的最终答案,又消耗了大量的空间。这个做法的时间复杂度和空间复杂度都很高,因此我们要换一种思路来考虑这个问题。

「不重复」的本质是什么?我们保持三重循环的大框架不变,只需要保证:

第二重循环枚举到的元素不小于当前第一重循环枚举到的元素;

第三重循环枚举到的元素不小于当前第二重循环枚举到的元素。

也就是说,我们枚举的三元组 (a, b, c) 满足 a≤b≤c,保证了只有 (a,b,c) 这个顺序会被枚举到,而 (b,a,c)、(c,b,a) 等等这些不会,这样就减少了重复。要实现这一点,我们可以将数组中的元素从小到大进行排序,随后使用普通的三重循环就可以满足上面的要求。

同时,对于每一重循环而言,相邻两次枚举的元素不能相同,否则也会造成重复。举个例子,如果排完序的数组为

[0, 1, 2, 2, 2, 3]

我们使用三重循环枚举到的第一个三元组为 (0, 1, 2),如果第三重循环继续枚举下一个元素,那么仍然是三元组 (0, 1, 2),产生了重复。因此我们需要将第三重循环「跳到」下一个不相同的元素,即数组中的最后一个元素 3,枚举三元组 (0, 1, 3)。

nums.sort()
for first = 0 .. n-1
    // 只有和上一次枚举的元素不相同,我们才会进行枚举
    if first == 0 or nums[first] != nums[first-1] then
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                for third = second+1 .. n-1
                    if third == second+1 or nums[third] != nums[third-1] then
                        // 判断是否有 a+b+c==0
                        check(first, second, third)

作者:LeetCode-Solution
链接:https://leetcode-cn.com/problems/3sum/solution/san-shu-zhi-he-by-leetcode-solution/
来源:力扣(LeetCode)
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。

改进:

nums.sort()
for first = 0 .. n-1
    if first == 0 or nums[first] != nums[first-1] then
        // 第三重循环对应的指针
        third = n-1
        for second = first+1 .. n-1
            if second == first+1 or nums[second] != nums[second-1] then
                // 向左移动指针,直到 a+b+c 不大于 0
                while nums[first]+nums[second]+nums[third] > 0
                    third = third-1
                // 判断是否有 a+b+c==0
                check(first, second, third)

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合,随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注