来源于LeetCode 第 15 题评论区
大家好，我是吴师兄。
前几天分享了字节最喜欢考察的前 50 题，其中三数之和的考察频率甚至排在前 10，不得不学。
题目描述很简单：
给你一个包含
n个整数的数组nums，判断nums中是否存在三个元素 a，b，c ，使得 a b c = 0 ？请你找出所有和为0且不重复的三元组。 注意：答案中不可以包含重复的三元组。
问题的核心是在一个数组中找出所有不重复的三个元素的组合，这三个元素的和为零。下面是对代码的逐步解释，以便于初学者理解每个部分的功能和目的。
- 排序: 首先，我们对数组进行排序。这是因为排序后的数组更容易处理，尤其是在我们寻找特定元素或者需要比较元素大小的时候。排序也有助于避免重复的解决方案。
- 外层循环: 我们使用一个循环来遍历数组中的每个元素。每次循环选定一个元素作为三元组的第一个元素。这个循环是整个解决方案的核心，它确保我们检查了数组中的每个元素。
- 避免重复: 为了避免找到重复的三元组，我们检查当前元素是否与前一个元素相同。如果相同，我们跳过这个元素，因为它会导致重复的解决方案。
- 左右指针: 对于每个外层循环选定的元素，我们设定两个指针，一个在当前元素之后，一个在数组末尾。这两个指针分别代表三元组中的另外两个元素。
- 查找和为零的三元组: 我们移动左右指针，寻找和为零的三个数。如果找到了，我们将这三个数添加到结果中。为了进一步避免重复，我们在找到一组解后，需要将左右指针移到新的位置，跳过重复的值。
- 左右指针的移动: 如果当前三个数的和小于零，我们将左指针向右移动，因为数组是排序的，这样可以增加三数之和。相反，如果和大于零，我们将右指针向左移动，以减少总和。
- 返回结果: 在检查了所有可能的组合后，我们返回结果。
这个解决方案的关键在于它使用了双指针方法。这种方法相比于暴力解法（三重循环检查所有可能的组合）要高效得多。通过排序数组和使用双指针，我们能够有效地避免不必要的重复检查，同时也能更快地找到所有符合条件的组合。
来看代码：
代码语言：javascript复制class Solution {
public static List<List<Integer>> threeSum(int[] nums) {
// 题目存在多组解，每一组解都是一个数组，所以使用二维数组存储所有的解
List<List<Integer>> ans = new ArrayList();
// 获取数组的程度
int len = nums.length;
// 边界情况判断
if(nums == null || len < 3) return ans;
// 先将数组进行排序操作，从小到大
Arrays.sort(nums);
// 开始遍历整个数组
// 在遍历的过程中，观察设置的三个位置的元素之后的大小
// num[i] 为从左到右观察过去的元素
// left 为从 i 到 len - 1 的元素
// right 为从 len - 1 向左移动到 i 的元素
for (int i = 0; i < len ; i ) {
// 如果发现 nums[i] > 0 ，由于 nums 是递增序列，left 在 nums[i] 的右侧，right 也在 nums[i] 的右侧
// 那么 num[i]、nums[left]、nums[right] 都大于 0
// 说明这三数之和一定大于 0 ，结束循环
if(nums[i] > 0) break;
// 答案中不可以包含重复的三元组，所以需要执行一个去重的操作
// 比如这个输入 [-4,-1,-1,0,1,2]
// i 指向的为第一个 -1 时，left 指向的元素值为 0 ，right 指向的元素值为 1
// i 指向的为第二个 -1 时，left 指向的元素值为 0 ，right 指向的元素值为 1
// 这两组解都是 [ -1 , 0 , 1]，所以需要去重
if(i > 0 && nums[i] == nums[ i - 1 ]) continue;
// left 为从 i 到 len - 1 的元素，向右移动
int left = i 1;
// right 为从 len - 1 向左移动到 i 的元素，向左移动
int right = len - 1;
// left 和 right 不断的向内移动
while(left < right){
// 计算这三者之和
int sum = nums[i] nums[left] nums[right];
// 发现三者之和为 0
if(sum == 0){
// 把这个结果记录一下
ans.add(Arrays.asList(nums[i],nums[left],nums[right]));
// 答案中不可以包含重复的三元组，所以需要执行一个去重的操作
// 比如这个输入 [-2,0,0,2,2]
// i 指向的元素值为 -2 ，left 指向的元素值为第一个 0 ，right 指向的元素值为倒数第一个 2 时
// 它们的 sum 为 0 ，如果让 ，left 向右移动一下，，right 向左移动一下，它们的 sum 也为 0
// 但是这两组解都是 [ -2 , 0 , 2]，所以需要去重
while( left < right && nums[left] == nums[ left 1 ]) {
// left 向右移动
left ;
}
while( left < right && nums[right] == nums[ right - 1]){
// right 向左移动
right--;
}
// left 向右移动
left ;
// right 向左移动
right--;
// 如果三者之和小于 0 ，那么说明需要找更大的数
}else if (sum < 0){
// left 向右移动
left ;
// 如果三者之和大于 0 ，那么说明需要找更小的数
}else if (sum > 0) {
// right 向左移动
right--;
}
}
}
// 返回结果
return ans;
}
}
我总结并录制了 100 道 LeetCode 高频算法题，涵盖了数组、链表、栈、队列、二叉树、回溯算法、动态规划等众多高频知识点，所选的题目也是非常有特征的题目，一题抵十题。
