来源于LeetCode 第 15 题评论区
大家好,我是吴师兄。
前几天分享了字节最喜欢考察的前 50 题,其中三数之和的考察频率甚至排在前 10,不得不学。
题目描述很简单:
给你一个包含
n
个整数的数组nums
,判断nums
中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为0
且不重复的三元组。 注意:答案中不可以包含重复的三元组。
问题的核心是在一个数组中找出所有不重复的三个元素的组合,这三个元素的和为零。下面是对代码的逐步解释,以便于初学者理解每个部分的功能和目的。
这个解决方案的关键在于它使用了双指针方法。这种方法相比于暴力解法(三重循环检查所有可能的组合)要高效得多。通过排序数组和使用双指针,我们能够有效地避免不必要的重复检查,同时也能更快地找到所有符合条件的组合。
来看代码:
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 高频算法题,涵盖了数组、链表、栈、队列、二叉树、回溯算法、动态规划等众多高频知识点,所选的题目也是非常有特征的题目,一题抵十题。