题目
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
规则示例
规则
0 <= nums.length <= 3000
-105 <= nums[ i ] <= 10的5次方
示例1
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例2
输入:nums = []
输出:[]
示例3
输入:nums = [0]
输出:[]
解题分析:排序+双指针
解决这道题的难点在于,不可以包含重复的三元组,那么这道题排重是关键。
如果我们在找目标之前,先对数组进行升序排序,那么我们在遍历该数组时,排重相对来说就好处理一些了,因为从左到右是有规律的。
如果循环嵌套过多会使该题的时间复杂度消耗过大,所以我们可以尝试使用双指针。
首先我们从左往右取出一个数,再用一个左右指针去取出后面的内容进行计算,这样可以有效的提升我的效率。
我们以 -1,0,1,2,-1,-4 为例
首先对其进行升序排序
-4, -1, -1, 0, 1, 2
从图中我们可以得到一些关键信息:
循环的过程中如果发现当前索引i对应值等于i-1对应,则排重继续循环
左右指针移动时,也要排重
如果发现 left + 1对应值 等于 left 对应值,则继续移动
如果发现 right - 1对应值 等于 right 对应值,则继续移动
每一轮的左右指针移动的结束条件是 left >= right 位置
解题:排序+双指针
END