三数之和
一题二写,三数之和,题解四瞅五瞄六瞧,水平还颠七倒八下九流,十分辣鸡。
题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:
- 答案中
不可以
包含重复的三元组。 - 0 <= nums.length <= 3000
- -105 <= nums[i] <= 105
测试用例
用例一
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
用例二
输入:nums = []
输出:[]
用例三
输入:nums = [0,0,0,0]
输出:[[0,0,0]]
解题思路
这道题目如果不考虑空间消耗/耗时等因素, 单纯的实现题目的要求, 实际不难, 比较容易就能实现, 比如暴力三个for循环处理, 但是提交代码之后 就是执行超时, 意味着执行时间是有问题的, 需要优化.
具体步骤如下:
- 将输入数据
升序 排序
- 将输入数据
- 从头遍历排序后的数组, 遇到当前值
大于0
, 即可结束
- 从头遍历排序后的数组, 遇到当前值
- 若当前不是第一个数, 并且当前值与前一个值相等, 跳过, 从下一个数值继续执行, 此步骤
过滤掉重复的结果
- 若当前不是第一个数, 并且当前值与前一个值相等, 跳过, 从下一个数值继续执行, 此步骤
- 使用两个指针, 一个从
当前数值后面第一位向右走
, 一个从尾部向左走
- 使用两个指针, 一个从
- 如果前后两个
相遇
后, 本轮循环结束
- 如果前后两个
- 同步骤3,左右两个指针依旧要检查重复值,
左边
指针遇到重复值向右
移动 ,右边
指针遇到重复值向左
移动
- 同步骤3,左右两个指针依旧要检查重复值,
- 计算
当前索引值
+左指针值
+右指针值
- 若
等于
0 , 记录当前的 三个值 , 同时,左指针右移, 右指针左移
- 若
大于
0 , 说明右指针
数值过大 ,右指针左移
- 若
小于
0 , 说明左指针
数值过小 ,左指针右
- 计算
代码实现
1 |
|
参考资料
[^1] : 15 - 三数之和
[^2] : 相似题目 - 16 - 最接近的三数之和
三数之和
http://www.zhangdeman.cn/archives/632d79b2.html