给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/3sum
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
暴力求解,3重循环.
时间复杂度:O(n^3)
这个解法超过了Leetcode的运行时间限制.无法提交.
先对nums排序(升序).平均时间复杂度O(n*log(n))
为了方便,我把a数字与a数字的数组下标混在一起说了.以下所有说到右移++、左移–,都指的是数组下标的操作.
设定a<b<c,第一重循环遍历a.
关键在第二重循环.b从a+1开始,自左向右递增.c从最右侧开始,自右向左递减.
综上,第二重循环可以概括为如下伪代码:
while(b<c && a+b+c>0) c--; if(b==c) //由于上面的if先判断b<c,因此这里要先过滤b==c的情况.不能与下边的if调换顺序 break; if(a+b+c==0) 存结果; c--; continue; else //a+b+c<0 break;
可以发现,b与c,一个向右,一个向左,直到两者相遇.它们的移动没有嵌套的循环关系.因此第二层循环的时间复杂度就是O(n).
再考虑第一层循环的嵌套关系,整体时间复杂度是O(n^2)