Leedcode三数之和 Python解析

本文涉及的产品
云解析 DNS,旗舰版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
全局流量管理 GTM,标准版 1个月
简介: Leedcode三数之和 Python解析

问题描述:


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


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


问题分析:1:不难想到转化成为两数之和的问题 -c=a+b


2:为了避免重复 先将原序列排序


例如 [-1,0,1,2,-1,-4]排序后[-4,-1,-1,0,1,2] 遍历数组每个元素 作为target(-c)


每次遍历就是求每一次新的target的两数之和问题


因而容易写出以下代码


class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        if len(nums)<3:
            return []
        else:
            answer=[]
            for i in range(0,len(nums)-1):
                target=nums[i]
                for j in range(i+1,len(nums)-1):
                    if -target-nums[j] in nums[j+1:]:
                        tmp=[target,min(-target-nums[j],nums[j]),max(-target-nums[j],nums[j])]
                        if  tmp not in answer:
                            answer+=[tmp]
        return answer


很遗憾 超时了 315/318


下面尝试利用双指针,进行优化分析:


image.png

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        nums.sort()
        if len(nums)<3:
            return []
        else:
            answer=[]
            for i in range(0,len(nums)-1):
                target=nums[i]
                if target>0:
                    break
                start,end=i+1,len(nums)-1
                while start<end:
                    if nums[start]+nums[end]+target==0:
                        tmp=[target,nums[start],nums[end]]
                        if tmp not in answer:
                            answer.append(tmp)
                        start+=1
                        end-=1
                    elif nums[start]+nums[end]+target>0:
                        end-=1
                    else:
                        start+=1
        return answer

image.png



我是小郑😀今天强化了双指针学习很高兴 期待与你一起进步


目录
相关文章
|
3月前
|
算法 Python
【Leetcode刷题Python】子数组查找
一个用于寻找给定字符串中最长重复子串的Python函数实现,采用了滑动窗口的方法来检测重复的子串。
20 1
|
3月前
|
Python
【Leetcode刷题Python】16. 最接近的三数之和
解决LeetCode "最接近的三数之和" 问题的Python实现,通过排序和双指针法,记录并更新与目标值最接近的三数之和。
36 1
|
3月前
|
Python
【Leetcode刷题Python】15. 三数之和
LeetCode "三数之和" 问题的Python实现代码,通过排序、双指针和跳过重复元素的方法找出所有和为0的不重复三元组。
20 0
|
5月前
|
存储 SQL 算法
LeetCode第53题:最大子数组和【python 5种算法】
LeetCode第53题:最大子数组和【python 5种算法】
|
5月前
|
SQL 算法 数据挖掘
LeetCode第十五题:三数之和【15/1000 python】
LeetCode第十五题:三数之和【15/1000 python】
|
存储 算法 Python
【力扣算法14】之 15. 三数之和 python
【力扣算法14】之 15. 三数之和 python
96 0
|
算法 Python
Python OJ题典例算法:最大子序和
本文介绍了使用动态规划思想解决最大子序和问题,并通过遍历数组的方式来求解。动态规划将问题拆分为多个阶段,通过前一阶段的最优解推导当前阶段的最优解。通过定义状态转移方程和初始条件,可以高效地求解最大子序和问题。
82 0
|
存储 算法 Python
【力扣算法16】之 18. 四数之和 python
【力扣算法16】之 18. 四数之和 python
86 0
|
机器学习/深度学习 存储 算法
【力扣算法08】之 5. 最长回文子串 python
【力扣算法08】之 5. 最长回文子串 python
134 0
|
Python
Leedcode三数之和 Python解析
Leedcode三数之和 Python解析
93 0
Leedcode三数之和 Python解析