蓝桥杯入门即劝退（二十一）三数之和（梦破碎的地方）

欢迎===关注===点赞===评论，共同学习，共同进步！

------持续更新蓝桥杯入门系列算法实例--------

如果你也喜欢Java和算法，欢迎订阅专栏共同学习交流！

你的点赞、关注、评论、是我创作的动力！

-------希望我的文章对你有所帮助--------

💪😳👍

一、题目描述

  给你一个整数数组 nums ，判断是否存在三元组 [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 。

二、解题思路

1、对于求三数之和需要注意的是返回的是一个元组，且不能重复，因此测试用例必然会出现许多重复的结果，需要在过程中剔除。
2、首先即使用Arrays数组内置排序模块进行升序排序，要求a+b+c=0,且a<b<c;
即a<0,a+b>0,或a+b>0,c<0;
且当a>0时，即不可能有sum为0，直接return掉。
3、采用双指针法，类似于二分查找，将num[0]设置为a,b则是其后一个元素，c为最大的元素。
4、开始二分遍历，首先剔除掉a的重复元素。
5、计算sum和，如果sum>0，说明值过大，则right指针左移使得整体值减小以接近0；
      如果sum<0,即值过小，要将left右移动以接近0；
6、当sum恰好为0时，将三个元素加入到列表中；
7、再次对b、c重复值进行剔除，且指针也要相应的移动实现剔除
8、最后返回结果即可。

三、代码实现

public List<List<Integer>> threeSum(int[] nums) {List<List<Integer>> result=new ArrayList<>();Arrays.sort(nums);int sum=0;for (int i=0;i< nums.length;i++){if (nums[i]>0)return result;if (i>0&&nums[i]==nums[i-1])continue;//跳过即剔除int left=i+1;//相当于左边界int rigth= nums.length-1;//相当于右边界while (rigth>left){sum=nums[i]+nums[left]+nums[rigth];if (sum>0)rigth--;else if (sum<0)left++;else {result.add(Arrays.asList(nums[i],nums[left],nums[rigth]));//加入列表while (rigth>left&&nums[rigth]==nums[rigth-1]) rigth--;//剔除重复的cwhile (rigth>left&&nums[left]==nums[left+1]) left++;//剔除重复的brigth--;//再次移动left++;}}}return result;}

发文不易，恳请大佬们高抬贵手！
点赞：随手点赞是种美德，是大佬们对于本人创作的认可！
评论：往来无白丁，是你我交流的的开始！
收藏：愿君多采撷，是大佬们对在下的赞赏！