发表文章

[最新] Leetcode 015 三数之和 思路详解+反思易错 Python实现

weixin41958153 4月前 1

本人一直在努力地积累Leetcode上用Python实现的题,并且会尽力讲清每道题的原理,绝不像其他某些博客简略地带过。

如果觉得讲的清楚,欢迎关注。


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

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

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

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

这道题的特点是:1.找出的数字只能出现一次,-1出现2次是因为本来数组中就有2个-1。

2.是一定要三个数加起来等于target,你只有一个数还不行。

以上都与之后的39组合总和不同。


思路:很容易想到了暴力法。但是这道题似乎有可以简化步骤的部分。首先我们需要对数组进行排序,这样的好处是:1.当某一项大于target了之后,与它有关的和都不用考虑了,因为排在它后面的数都比它大,三个大于Target的数的和一定大于target(正数情况下)。2.我们能让相等的数靠在一起。相等的数靠在一起有什么好处?答:相同的数我只考虑一次,因为要避免最后的集合有重复。3.排序后我们可以用三个指针来做,其中一个指针遍历,另2个指针往中间夹,其中一个指针往右移变大,另一个指针往左移变小,不至于说2个都变大或变小,离target越来越远。

代码及详细注释:

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        #建立一个空的结果list
        res_list = []
        #对数组排序
        nums.sort()
        #对第一个指针遍历,在思路里说过
        for i in range(len(nums)):
            #第二个指针
            j = i + 1
            #第三个指针
            k = len(nums)- 1
            #第一个最小的数都大于0了,我们后面就不用求了
            if nums[i] > 0:
                break
            if i > 0 and nums[i-1] == nums[i]:
                continue
            #相等的数的符合条件的解在前一个值上已经被求过了
            #往中间夹逼
            while j < k:
                #如果刚好符合条件?
                ans = nums[i] + nums[j] + nums[k]
                if ans == 0:
                    #跳过相同的数
                    res_list.append([nums[i], nums[j], nums[k]])
                    while j < k and nums[j] == nums[j+1]:
                        j += 1
                    while j < k and nums[k] == nums[k-1]:
                        k -= 1
                    #最终都要指向下一个
                    k -= 1
                    j += 1
                #因为数组的有序性,所以我们面对小于Target的情况,应该增大我们目前的值,所以加大j
                elif ans < 0:
                    j += 1
                #同理
                else:
                    k -= 1

        return res_list

总结:1.Leetcode 的时间限制很严格,比如说我们这个程序,如果你在算三个指针的和的时候没有一次性算完,没有用ans去储存结果,那么会超时。

2.暴力法可以简化,思路本身没有问题,去重可以让我们速度更快

3.排序数组带给我们的便利非常大。


相关推荐
最新评论 (0)
返回
发表文章
weixin41958153
文章数
90
评论数
0
注册排名
979951