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版本

历史上的今天:


繁夜