一、题目
给你一个整数数组 nums
,判断是否存在三元组 [nums[i], nums[j], nums[k]]
满足 i != j
、i != k
且 j != k
,同时还满足 nums[i] + nums[j] + nums[k] == 0
。请你返回所有和为 0
且不重复的三元组。
注意:答案中不可以包含重复的三元组。
二、示例
2.1> 示例 1:
【输入】nums = [-1,0,1,2,-1,-4]
【输出】[[-1,-1,2],[-1,0,1]]
【解释】
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0 。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0 。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0 。
不同的三元组是 [-1,0,1] 和 [-1,-1,2] 。
注意,输出的顺序和三元组的顺序并不重要。
2.2> 示例 2:
【输入】nums = [0,1,1]
【输出】[]
【解释】唯一可能的三元组和不为 0
2.3> 示例 3:
【输入】nums = [0,0,0]
【输出】[[0,0,0]]
【解释】唯一可能的三元组和为 0
提示:
3
<= nums.length <=3000
-10^5
<= nums[i] <=10^5
三、解题思路
根据题意,我们要找到满足nums[i] + nums[j] + nums[k] == 0
的三元组,那么如果3个数之和等于0,我们可以得出如下两个结论:
【结论1】3个数字的值都是0;
【结论2】3个数字中有正数也有负数;
基于如上分析,我们为了便于进行遍历计算,我们先将nums
中的数字进行排序操作。然后我们通过指针i
去遍历整个排序后的数组,与此同时,我们创建两个指针p
和q
,p指向i+1的位置,q执行数组的末尾。通过nums[i] + nums[p] + nums[q]
我们可以得到总和sum
,然后我们进行如下逻辑判断:
【如果sum等于0】则满足题目中的条件,将其放入到List中,后续作为返回值;
【如果sum大于0】我们需要向左移动q指针,因为这样q会变小,整体的sum值也会变小更加趋近于0;
【如果sum小于0】我们需要向右移动p指针,因为这样p会变大,整体的sum值也会变大更加趋近于0;
除了上面的逻辑,我们还需要注意去重的操作,也就是说,当我们移动i指针、p指针或q指针的时候,如果发现待移动的位置数字与当前数字相同,那么就跳过去继续指向下一个元素,直到找到与当前数字不同的数字为止(当然,要避免数组越界)。在移动p指针和q指针的过程中,如果不满足p。
以上就是本题的解题思路,我们可以通过一个示例来看一下具体的操作过程,由于篇幅问题,如下我仅画出了部分的计算逻辑,但是并不影响整体的逻辑判断。我们以入参为nums = [-1,0,1,2,-1,-4]
为例,看一下下面的具体处理逻辑:
nums[0]
逻辑执行完毕后,我们再来执行nums[1]
的计算逻辑,并以此类推,直到遍历完整个数组nums
。
四、代码实现
class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> result = new ArrayList(); Arrays.sort(nums); for (int i = 0; i < nums.length && nums[i] <= 0; i++) { if (i > 0 && nums[i - 1] == nums[i]) continue; int p = i + 1, q = nums.length - 1; while (p < q && nums[q] >= 0) { int iv = nums[i], qv = nums[q], pv = nums[p], sum = iv + pv + qv; if (sum == 0) result.add(Arrays.asList(iv, pv, qv)); if (sum > 0) while (q > 0 && nums[q] == qv) q--; else while (p < nums.length - 1 && nums[p] == pv) p++; } } return result; } }
今天的文章内容就这些了:
写作不易,笔者几个小时甚至数天完成的一篇文章,只愿换来您几秒钟的 点赞 & 分享 。
更多技术干货,欢迎大家关注公众号“爪哇缪斯” ~ \(^o^)/ ~ 「干货分享,每天更新」