图解LeetCode——15. 三数之和
一、题目
给你一个整数数组 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<q，则结束本轮操作即可。
以上就是本题的解题思路，我们可以通过一个示例来看一下具体的操作过程，由于篇幅问题，如下我仅画出了部分的计算逻辑，但是并不影响整体的逻辑判断。我们以入参为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)/ ~ 「干货分享，每天更新」
