![[hot100]三数之和](images/page-header-bg.jpg)
![[hot100]三数之和](http://pic.xiahunao.cn/yaotu/[hot100]三数之和)
三数之和附上卡尔大神的讲解梦破碎的地方| LeetCode15.三数之和_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1GW4y127qo/?spm_id_from333.1391.0.0vd_source9eb6e4de48672f76da98b479d4a96f25题目的大概意思就是从一个数组里面找到三个数值加起来为0的三个数 然后题目要求三元组之间不能重复 但是组内是可以重复的eg[-1,-1,2]就是满足条件的三元组 [2,1,-3]也是 但是不能出现两个[-1,-1,2] 三元组内部的数字可以重复题目要求返回一个二维数组 也就是一个满足条件的三元组数组这里题目没有要求返回索引 这里就要想到可以排序来提高我们的信息熵 增加信息这道题其实细节方面是有点复杂的 难点在于如何确定三个数的信息 上面说排序提高信息 就是让这个数组能够按照一定的顺序排列来提高信息 这里我们要找到abc0的abc三元组 意味着需要三个变量 这个时候我们就需要联想到双指针加上一个变量 不过经验和想法这东西都还是根据刷题经验以及长期积累来的 所以这题是有一定难度的 这个不太好想 就是三个变量 刚好就是双指针加上一个循环变量所以abc就可以拆解成 固定a 让bc-a 这里的a就是每一步循环遍历循环的i然后b和c就是两头的双指针所以思路就是遍历nums数组 让a固定 然后b指向i下一个 c指向末尾然后根据三者之间的和来收缩指针 这里为什么能够根据三者之和来收缩指针呢 因为我们的这个数组是带有信息的 也就是排序过的 这也就是为什么我们上面要先把数组排列然后再遍历根据sum来判断两个指针如何来移动 如果sum0 这个时候说明数小了 就把左边的指针往右移动 让它数值大一些如果sum0 说明数大了 就把右边的指针往左移动 让它数值小一些如果0 这个时候说明当前的i b c 就是我们想要寻找的三元组 我们就可以把它add进list 然后同时收缩两个指针 但是我们这个时候需要注意的是题目要求我们不能有重复的三元组 所以需要去重 这个时候我们就要去重 要对 i b c都要去重对i用nums[i]nums[i-1]来判断是否重复注意这里为什么不能是nums[i]nums[i1]因为left指针就是i1 也就是i前面一位如果用这个来判断的话就是来判断一个数组里面是否有重复的了eg这个情况下 i 和left指向的就是相等的 但是这个是符合条件的 因为nums[i]nums[i1]这个本质就是用i和left指向的来做比较 但是i和left是可以进行比较的所以只能用nums[i]nums[i-1]同理用nums[left]nums[left-1]和nums[right]nums[right1]来进行去重 这里的right就是要去和右边的比了 因为左边 也就是right-1可能是left 但是left可以等于right还可以对代码进行一个剪枝 也就是当i指向的元素都大于0的情况下 可以直接返回list数组了 因为left和right指向的都大于i指向的 这个时候后续移动三者不可能三者相加等于0 所以可以直接返回 这里根据排序之后和位置关系得出的条件是nums[i]nums[left]nums[right]if nums[i]0nums[i]nums[left]nums[right] !0所以直接返回之前找到的三元组即可但是这里一定要注意的是返回不能写成 new Arraylist 因为这个返回的是一个空数组 没有返回到有数组的listimport java.util.*; public class Main { public static void main(String[] args) { Scanner input new Scanner(System.in); String s input.nextLine(); String[] split s.split( ); int [] arrnew int[split.length]; for (int i 0; i split.length; i) { arr[i]Integer.parseInt(split[i]); } ListListInteger lists threeSum(arr); for (int i 0; i lists.size(); i) { System.out.println(lists.get(i)); } } public static ListListInteger threeSum(int[] nums) { //先对nums进行排序 Arrays.sort(nums); //然后在开始循环遍历nums ArrayListListInteger list new ArrayList(); for (int i 0; i nums.length; i) { //剪枝 如果到了i这里数值开始大于0了 后面的left和right肯定也是大于0的 这三者后面的和肯定不会为0 //所以可以直接返回 if(nums[i] 0){ return list; } //对i进行去重 if(i0nums[i]nums[i-1]){ continue; } //定义两个指针 放在后续数组的两段 int lefti1; int rightnums.length-1; while(leftright){ int sumnums[i]nums[left]nums[right]; if(sum0){ list.add(Arrays.asList(nums[i],nums[left],nums[right])); //移动双指针 left; right--; //对两个指针进行去重 while(leftrightnums[left]nums[left-1]){ left; } while(leftrightnums[right]nums[right1]){ right--; } }else if(sum0){ right--; }else{ left; } } } return list; } }如果有什么问题可以评论区一起讨论一下 如果觉得写的还可以点个赞鼓励一下谢谢
