LeetCode: 15. 3Sum

引言

题目链接:https://leetcode.com/problems/3sum/description/

题目大意

给出一个包含n个整数的数组nums,这个数组是否存在元素有a,b,c使得 a + b + c = 0,找出所有满足条件的a,b,c的组合

  • Example

题解

很容易想到暴力解法,三重循环穷举所有可能进行判断,但很明显这种方法会超时,想一想有什么办法能够优化不必要的循环?

排序

将数组排序,从起始点进行大小长度为三的滚动判断即可,这样就好像省去了两重循环,事件复杂度变成了 O(3*n)?

由于数字可能为负数,所以选取当前有序数组两端的数字更可能构成目标数字零,所以数字的滚动不应该选取连续的。

选择一个标志点作为第一个数字从零开始往后推进,从当前标志位往后剩余数组两端选取剩余两个目标数字进行判断,并不断往中间压缩判断即可(由于数组有序,剩余两个数在当前位置之后寻找,只要第一个数字不断推进直到结束,过程中可以覆盖所有解)

具体压缩判断条件如下:

每次根据当前选取三个数字的和和目标值0比较,大于目标值0,第三个数字从剩余数组从后往前选取,小于目标值0,第二个数字从剩余数组从前往后选取,每次选定三个目标值后将数字的和和目标值0比较,满足条件存储即可

复杂度

时间复杂度 O(n^2)

空间复杂度 O(1)

AC代码

c++版本

go版本

历史上的今天:

繁夜

发表评论


:[微笑]::[撇嘴]::[色]::[发呆]::[得意]::[流泪]::[害羞]::[闭嘴]::[睡]::[大哭]::[尴尬]::[发怒]::[调皮]::[呲牙]::[惊讶]::[难过]::[酷]::[冷汗]::[抓狂]::[吐]::[偷笑]::[可爱]::[白眼]::[傲慢]::[饥饿]::[困]::[惊恐]::[流汗]::[憨笑]::[大兵]::[奋斗]::[咒骂]::[疑问]::[嘘...]::[晕]::[折磨]::[衰]::[骷髅]::[敲打]::[再见]::[擦汗]::[抠鼻]::[鼓掌]::[糗大了]::[坏笑]::[左哼哼]::[右哼哼]::[哈欠]::[鄙视]::[委屈]::[快哭了]::[阴险]::[亲亲]::[吓]::[可怜]::[笑哭]::[doge]::[泪奔]::[无奈]::[托腮]::[斜眼笑]::[喷血]::[惊喜]::[骚扰]::[小纠结]::[我最美]::[羊驼]::[幽灵]::[吃]::[OK]::[爱你]::[抱拳]::[勾引]::[强]::[弱]::[拳头]::[爱心]::[喝彩]::[西瓜]::[啤酒]::[玫瑰]::[凋谢]::[礼物]::[拥抱]::[月亮]::[菊花]::[棒棒糖]::[蛋]::[刀]::[菜刀]::[炸弹]::[手枪]:

刷新评论