【边学边敲边记】LeetCode006:三数之和

简介: 【边学边敲边记】LeetCode006:三数之和

简说Python,号主老表,Python终身学习者,数据分析爱好者,从18年开始分享Python知识,原创文章227篇,写过Python、SQL、Excel入门文章,也写过Web开发、数据分析文章,老表还总结整理了一份2022Python学习资料和电子书资源,关注后私信回复:2022 即可领取。

image.png

一、写在前面

上一题传输门:LeetCode005:最长公共前缀

今天给大家分享的是LeetCode 数组与字符串 第六题:三数之和,为面试而生,期待你的加入。

二、今日题目

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

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

示例:

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

满足要求的三元组集合为:

[
  [-1, 0, 1],
  [-1, -1, 2]
]

三、 分析

看到这个题目第一眼,我想到的就是两数之和,咋一眼感觉上没有太大区别,实际是二维空间和三维空间的区别,最开始想的是和两数之和方法类似,这里我只要找到两数之和的相反数是不是在列表就行了,但真的实践起来,比较麻烦,时间复杂度先不说,就是思想上随便一说都是个麻烦事情,所以X先生果断放弃了这样掉头发不讨好的方法,换了一种思想,头+尾搜索法:头部循环,尾部从两端向中间搜索,思想如下:

image.png

我的思想

四、解题

  • 我的方法:
    从从中心向外扩散,时间复杂度:小于O(n^2)

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        # 列表排序,从小到大
        nums.sort()
        # [-4, -1, -1, 0, 1, 2]
        res_list = []
        # 头部循环查找
        for i in range(len(nums)):
            if i == 0 or nums[i] > nums[i - 1]:
                # 最左端
                l = i + 1  
                # 最右端
                r = len(nums) - 1
                while l < r:  # 正在查找
                    three_sum = nums[i] + nums[l] + nums[r]
                    if three_sum == 0:
                        res_list.append([nums[i], nums[l], nums[r]])
                        l += 1 # 右移一位
                        r -= 1 # 左移一位
                        while l < r and nums[l] == nums[l - 1]:
                            # 从左往右,相同数值直接跳过
                            l += 1
                        while r > l and nums[r] == nums[r + 1]:
                            # 从右往左,相同数值直接跳过
                            r -= 1
                    elif three_sum > 0:
                        # 大于零,右边数值大,左移
                        r -= 1
                    else:
                        # 小于零,左边数值小,右移
                        l += 1
        return res_list
  • 提交结果

image.png

提交结果


测试数据:313组
运行时间:740ms
击败人百分比:81.35%

五、疑惑

这里说一下上一篇最长公共前缀大牛方法中的zip()。

zip() 函数用于将可迭代的对象作为参数,将对象中对应的元素打包成一个个元组,然后返回由这些元组组成的列表。

如果各个迭代器的元素个数不一致,则返回列表长度与最短的对象相同,利用 * 号操作符,可以将元组解压为列表。

zip 方法在 Python 2 和 Python 3 中的不同:在 Python 3.x 中为了减少内存,zip() 返回的是一个对象。如需展示列表,
需手动 list() 转换。

六、结语

坚持 and 努力 : 终有所获。

目录
打赏
0
0
0
0
2
分享
相关文章
|
2月前
|
Leetcode第十五题(三数之和)
LeetCode第十五题“三数之和”要求在一个整数数组中找出所有不重复的三元组,使得它们的和为0,通常通过先排序再使用双指针法来解决。
41 0
Leetcode第十五题(三数之和)
第五天_双指针【算法入门】
第五天_双指针【算法入门】
56 0
代码随想录算法训练营第四十天 | LeetCode 343. 整数拆分、96. 不同的二叉搜索树
代码随想录算法训练营第四十天 | LeetCode 343. 整数拆分、96. 不同的二叉搜索树
59 1
代码随想录算法训练营第二十九天 | 回溯算法总结
代码随想录算法训练营第二十九天 | 回溯算法总结
53 0
【算法挨揍日记】day04——15. 三数之和、18. 四数之和
题目描述: 给你一个整数数组 nums ,判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ,同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
78 0
算法刷题第五天:双指针--4
链表的缺点在于不能通过下标访问对应的元素。因此我们可以考虑对链表进行遍历,同时将遍历到的元素依次放入数组A中。如果我们遍历到了N个素,那么链表以及数组的长度也为N,对应的中间节点即为A[N/2] 。
101 1
算法刷题第五天:双指针--4
AI助理

阿里云 AI 助理已上线!

快来体验一下吧。