优化网站广告优化,代理网站备案收钱,电子商务网站规划与建设摘要,房地产新闻时事热点1.问题描述 给你一个整数数组 nums #xff0c;判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k #xff0c;同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意 答案中不可以包含重复的三元组 示例1 输入判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i ! j、i ! k 且 j ! k 同时还满足 nums[i] nums[j] nums[k] 0 。请你返回所有和为 0 且不重复的三元组。 注意 答案中不可以包含重复的三元组 示例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 输入nums [0,1,1]
输出[]
解释唯一可能的三元组和不为 0 。 示例3 输入nums [0,0,0]
输出[[0,0,0]]
解释唯一可能的三元组和为 0 。 提示
3 nums.length 3000-105 nums[i] 105 难度等级 中等 题目链接 三数之和
2.解题思路 这道题叫做三数之和可以看做两数之和的升级版不过我没办法用两数之和的hash方法来做了。这一次我选择了双指针遍历。可能你会疑惑不是三数之和吗怎么是双指针法其实我们只要把其中一个数固定下来那不就是回归两个数了吗?两个数当然就是双指针法了。 首先我们得定义一个List集合来存储结果还要对数组进行排序(使用双指针法的前提)。 //用来存储结果ListListInteger result new ArrayList(); 接着我们就可以开始数组的遍历了。for循环先固定第一个数这里固定数也是有讲究的因为它要求的是三个数和为0。我们已经对数组进行排序了所以小的数肯定在前面大的数肯定在后面如果我们的第一个数就已经大于0了那么后面两个数必定大于0也就不可能三个数相加为0所以直接结束就好了。 //第一个数就大于0那三个数不可能加起来和为0if(nums[i] 0){break;} 如果第一个数小于0且索引不为0(防止数组越界)的话因为题目告诉我们不包含重复的三元组所以我们的第一个数要跳过已经使用过的数。又因为我们是排好序的所以相同的数就在数本身的前后我们只需要判断当前的数是否和前面的那个数相等就好了相等我们就跳过避免重复。 //除去相同的整数if(i 0 nums[i] nums[i-1]){continue;} 经过两轮排查之后我们终于固定下来了第一个数剩下的两个数我们就要从第一个数后面开始找了。定义左右两个指针左指针从第一个数旁边开始向后走右指针从数组的末端向前走一个在可选范围内最小一个在可选范围内最大。然后两个指针尝试靠拢每一次移动都计算一下三数之和是否为0。 //左右指针相互靠拢int left i1;int right nums.length - 1; 如果三数之和大于0说明加多了右指针所指的数较大要将右指针往左移减小一点如果三数之和小于0说明加少了左指针所指的数较小要将左指针往右移如果三数之和等于0那么就将这是哪个数存入一开始定义的List集合中。 //计算当前的三数之和int sum nums[i] nums[left] nums[right];if(sum 0){//sum 0,说明加多了右指针要往左移right--;continue;}else if(sum 0){//sum 0 ,说明加少了左指针要往右移left;continue;}//若走到这一步说明三数之和为0ListInteger data new ArrayList();data.add(nums[i]);data.add(nums[left]);data.add(nums[right]);result.add(data); 找到一组三数之和后不要着急着找第二组因为题目要求不能有重复的三元组所以我们还要将左右指针旁边与它们相同的数先跳过之后再找下一组。
//跳过与左指针相同的整数while(left right nums[left] nums[left 1]){left;}//跳过与右指针相同的整数while(left right nums[right] nums[right- 1]){right--;} 让左右指针不断靠拢直到左右指针相遇找到我们所固定的第一个数的所有可能。 //左右指针继续靠拢left;right--; 之后重复上述操作再重新固定一个新的数左右指针继续移动找到将所有的数遍历完或者遇到第一个数大于0的情况退出循环我们就找到了我们想要的所有结果。
3.代码展示
class Solution {public ListListInteger threeSum(int[] nums) { //用来存储结果ListListInteger result new ArrayList();//对整数数组进行排序Arrays.sort(nums);for(int i 0;i nums.length;i){//第一个数就大于0那三个数不可能加起来和为0if(nums[i] 0){break;}//除去相同的整数if(i 0 nums[i] nums[i-1]){continue;}//左右指针相互靠拢int left i1;int right nums.length - 1;while(left right){//计算当前的三数之和int sum nums[i] nums[left] nums[right];if(sum 0){//sum 0,说明加多了右指针要往左移right--;continue;}else if(sum 0){//sum 0 ,说明加少了左指针要往右移left;continue;}//若走到这一步说明三数之和为0ListInteger data new ArrayList();data.add(nums[i]);data.add(nums[left]);data.add(nums[right]);result.add(data);//跳过与左指针相同的整数while(left right nums[left] nums[left 1]){left;}//跳过与右指针相同的整数while(left right nums[right] nums[right- 1]){right--;}//左右指针继续靠拢left;right--;}}return result;}
}
4.总结 我觉得这道题的难点就在于能不能想到将数组进行排序和把一个数固定下来将三数之和简化为两数之和。一旦想到之后采用左右指针获取所有结果这些操作都不难想到了。同时还要记得要跳过那些相同的整数。好了这道题就bb到这了祝大家刷题愉快~
