Leedcode三数之和 Python解析

本文涉及的产品
云解析 DNS,旗舰版 1个月
全局流量管理 GTM,标准版 1个月
公共DNS(含HTTPDNS解析),每月1000万次HTTP解析
简介: 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】5. 最长回文子串
LeetCode 5题 "最长回文子串" 的Python解决方案,使用动态规划算法找出给定字符串中的最长回文子串。
43 3
|
3月前
|
Python
【Leetcode刷题Python】53. 最大子数组和
LeetCode第53题"最大子数组和"的Python解决方案,利用动态规划的思想,通过一次遍历数组并维护当前最大和以及全局最大和来求解。
87 2
|
3月前
|
存储 Python
【Leetcode刷题Python】64. 最小路径和
一种使用动态规划解决LeetCode上64题“最小路径和”的Python实现方法,通过维护一个一维数组来计算从网格左上角到右下角的最小路径总和。
32 1
【Leetcode刷题Python】64. 最小路径和
|
3月前
|
算法 Python
【Leetcode刷题Python】子数组查找
一个用于寻找给定字符串中最长重复子串的Python函数实现,采用了滑动窗口的方法来检测重复的子串。
19 1
|
3月前
|
Python
【Leetcode刷题Python】16. 最接近的三数之和
解决LeetCode "最接近的三数之和" 问题的Python实现,通过排序和双指针法,记录并更新与目标值最接近的三数之和。
33 1
|
3月前
|
Python
【Leetcode刷题Python】343. 整数拆分
LeetCode 343题 "整数拆分" 的Python解决方案,使用动态规划算法来最大化正整数拆分为多个正整数之和的乘积。
26 0
|
3月前
|
Python
【Leetcode刷题Python】15. 三数之和
LeetCode "三数之和" 问题的Python实现代码,通过排序、双指针和跳过重复元素的方法找出所有和为0的不重复三元组。
18 0
|
3月前
|
Python
【Leetcode刷题Python】191. 位1的个数
本文提供了LeetCode题目191的Python编程解决方案,题目要求编写一个函数来计算一个无符号整数的二进制表示中1的个数,即汉明重量。
10 0
|
5月前
|
存储 SQL 算法
LeetCode第53题:最大子数组和【python 5种算法】
LeetCode第53题:最大子数组和【python 5种算法】
|
5月前
|
SQL 算法 数据挖掘
LeetCode第十五题:三数之和【15/1000 python】
LeetCode第十五题:三数之和【15/1000 python】