题目
https://leetcode.com/problems/3sum/description/
想法
可以说是很经典了。
最naive的方式,三层循环,遍历,O( n^3 ), 肯定不行
先排序,超过了就break,能省一点时间
唉,还有重复的问题呢,答案不能重复
哎呀,不想了,直接看答案吧,这种问题,肯定是那种知道解法之后,终身不忘的
O( N^2 )的解法:
排序
从左往右遍历,确定第一个数A[i]
对于第二个数和第三个数,分别是A[i + 1]和A[n - 1],一头一尾
如果相加为0,输出
如果大了,右边的往左走,否则,左边往右走
关于重复问题需要判断一下,需要判断一下,找到下一个不重复的
答案
|
|
这里,重复的判断,就是遇到重复的,就继续向前走,直到不重复!