LeetCode如何解决三数之和问题

这篇文章主要介绍LeetCode如何解决三数之和问题，文中介绍的非常详细，具有一定的参考价值，感兴趣的小伙伴们一定要看完！

创新互联建站专注于滦平网站建设服务及定制，我们拥有丰富的企业做网站经验。热诚为您提供滦平营销型网站建设，滦平网站制作、滦平网页设计、滦平网站官网定制、小程序设计服务，打造滦平网络公司原创品牌,更为您提供滦平网站排名全网营销落地服务。

题目描述

给定一个整数数组nums，判断nums中是否存在三个元素 a，b，c ，使得 a + b + c = 0 。如不存在返回[]，如存在返回所有满足条件且不重复的答案。如：输入[-1,0,1,2,-1,-4]返回[[-1,0,-1],[-1,-1,2]]，如输入[-3,3]，返回[]。

解题

本题需有两点预判：1、当数组长度小于3时，直接输出[]；2、对数组首先进行排序，如当前数字与前一个相同，所得结果也将一致，直接跳过即可。

思路一：哈希表

本题要找到满足条件的三个元素，当固定第一个元素a，则题目转化成找到b、c使得和为-a的问题，即与LeetCode刷题DAY 8：两数之和中问题一致，因此也可用哈希表的方法解决。

class Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:        if len(nums)<3:            return []        nums = sorted(nums)        a = list()        for i in range(len(nums)-2):            if i>0 and nums[i]==nums[i-1]:                continue            h_map = {}            target = -nums[i]            for j in range(i+1,len(nums)):                if target - nums[j] in h_map:                    a.append(sorted([nums[i],nums[j],target-nums[j]]))                h_map[nums[j]]=j        return list(set([tuple(t) for t in a]))

思路二：双指针

当对数组完成排序并固定第一个元素a，则题目与LeetCode刷题DAY 9：两数之和II中问题一致，可用双指针方法解决。

class Solution:    def threeSum(self, nums: List[int]) -> List[List[int]]:        if len(nums)<3:            return []        nums = sorted(nums)        a = list()        for i in range(len(nums)-2):            if i>0 and nums[i]==nums[i-1]:                continue            x = i+1            y = len(nums)-1            target = -nums[i]            while x<y:                if nums[x]+nums[y] == target:                    a.append(sorted([nums[i],nums[x],nums[y]]))                    x += 1                elif nums[x]+nums[y] < target :                    x += 1                else:                    y -= 1        return list(set([tuple(t) for t in a])

以上是“LeetCode如何解决三数之和问题”这篇文章的所有内容，感谢各位的阅读！希望分享的内容对大家有帮助，更多相关知识，欢迎关注创新互联行业资讯频道！

网站标题：LeetCode如何解决三数之和问题
链接分享：https://www.cdcxhl.com/article32/pgissc.html

成都网站建设公司_创新互联，为您提供App开发、网站内链、品牌网站制作、网站设计公司、企业建站、面包屑导航

声明：本网站发布的内容（图片、视频和文字）以用户投稿、用户转载内容为主，如果涉及侵权请尽快告知，我们将会在第一时间删除。文章观点不代表本网站立场，如需处理请联系客服。电话：028-86922220；邮箱：631063699@qq.com。内容未经允许不得转载，或转载时需注明来源：创新互联

猜你还喜欢下面的内容