当前位置:首页 » 《随便一记》 » 正文

【Leetcode刷题】15. 三数之和_202xxx的博客

12 人参与  2021年12月30日 12:17  分类 : 《随便一记》  评论

点击全文阅读


题目

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

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

示例1

输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]

示例2

输入:nums = []
输出:[]

示例3

输入:nums = [0]
输出:[]

提示

(1)0 <= nums.length <= 3000

(2)-105 <= nums[i] <= 105

解题思路

(1)对输入的nums中遍历获取第一个数,相同时跳过

(2)在第一个数右边遍历获取第二个数,相同时跳过

(3)在右边开始往回找第三个数,但是要保证第三个数在第二个数右边

(4)如果找到三个数加起来的和为0,则记录进ans

(5)最后输出ans

代码

class Solution:
    def threeSum(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        nums.sort()
        ans = list()
        
        # 枚举 a
        for first in range(n):
            # 需要和上一次枚举的数不相同
            if first > 0 and nums[first] == nums[first - 1]:
                continue
            # c 对应的指针初始指向数组的最右端
            third = n - 1
            target = -nums[first]
            # 枚举 b
            for second in range(first + 1, n):
                # 需要和上一次枚举的数不相同
                if second > first + 1 and nums[second] == nums[second - 1]:
                    continue
                # 需要保证 b 的指针在 c 的指针的左侧
                while second < third and nums[second] + nums[third] > target:
                    third -= 1
                # 如果指针重合,随着 b 后续的增加
                # 就不会有满足 a+b+c=0 并且 b<c 的 c 了,可以退出循环
                if second == third:
                    break
                if nums[second] + nums[third] == target:
                    ans.append([nums[first], nums[second], nums[third]])
        
        return ans

Reference

题库 - 力扣 (LeetCode) 全球极客挚爱的技术成长平台


点击全文阅读


本文链接:http://m.zhangshiyu.com/post/32404.html

个数  枚举  指针  
<< 上一篇 下一篇 >>

  • 评论(0)
  • 赞助本站

◎欢迎参与讨论,请在这里发表您的看法、交流您的观点。

最新文章

  • [糙汉嘴软心硬,娇妻日日晚起]小说精彩节选免费试读_「黎夏顾卫城」主线最终章倒计时
  • 我的亲妹妹我当做畜生,只有儿子来救我反转剧情试读片段_[***小宝李小翠]精彩章节免费试读
  • 往梦难复温,沈淮霆宋思予在线_往梦难复温,沈淮霆宋思予在线
  • 爱意清浅随风离(简凝夕陆靳燃),爱意清浅随风离
  • 「冲喜而已,侯爷别太爱」小说免费在线阅读_侯府侯爷乐瑶主线最终章倒计时
  • 好看的往梦难复温沈淮霆宋思予_往梦难复温沈淮霆宋思予
  • 天才京剧花旦被废嗓后成为芭蕾舞王+后续+结局(秦意宋笙)全书秦意宋笙结局_秦意宋笙+结局列表_笔趣阁(天才京剧花旦被废嗓后成为芭蕾舞王+后续+结局)
  • (番外)+(全书)往梦难复温(沈淮霆宋思予+番外+全书)_(往梦难复温+番外+全书)免费_笔趣阁(沈淮霆宋思予)
  • 江晚烟陆聿我终于失去了你结局+番外(江晚烟陆聿)列表_江晚烟陆聿我终于失去了你结局+番外(江晚烟陆聿)结局篇+番外在线
  • 池雾陆砚寒结局+番外(陆砚寒池雾)列表_池雾陆砚寒结局+番外(陆砚寒池雾)池雾陆砚寒结局+番外在线
  • 沈静怡傅励行+后续+结局(傅励行沈静怡)列表_沈静怡傅励行+后续+结局(傅励行沈静怡)沈静怡傅励行+后续+结局在线
  • 非典时,我被妻子的白月光误诊遗弃在病房节选角色羁绊特辑‌_田越苏雅白月光角色专属支线试读入口

    关于我们 | 我要投稿 | 免责申明

    Copyright © 2020-2022 ZhangShiYu.com Rights Reserved.豫ICP备2022013469号-1