[hot100]三数之和

三数之和

附上卡尔大神的讲解

梦破碎的地方！| LeetCode：15.三数之和_哔哩哔哩_bilibilihttps://www.bilibili.com/video/BV1GW4y127qo/?spm_id_from=333.1391.0.0&vd_source=9eb6e4de48672f76da98b479d4a96f25

题目的大概意思就是从一个数组里面找到三个数值加起来为0的三个数 然后题目要求三元组之间不能重复 但是组内是可以重复的

eg：[-1,-1,2]就是满足条件的三元组 [2,1,-3]也是 但是不能出现两个[-1,-1,2] 三元组内部的数字可以重复

题目要求返回一个二维数组 也就是一个满足条件的三元组数组

这里题目没有要求返回索引 这里就要想到可以排序来提高我们的信息熵 增加信息，

这道题其实细节方面是有点复杂的 难点在于如何确定三个数的信息 上面说排序提高信息 就是让这个数组能够按照一定的顺序排列来提高信息 这里我们要找到a+b+c=0的abc三元组 意味着需要三个变量 这个时候我们就需要联想到双指针加上一个变量 不过经验和想法这东西都还是根据刷题经验以及长期积累来的 所以这题是有一定难度的 这个不太好想 就是三个变量 刚好就是双指针加上一个循环变量

所以a+b+c就可以拆解成 固定a 让b+c=-a 这里的a就是每一步循环遍历循环的i，然后b和c就是两头的双指针

所以思路就是遍历nums数组 让a固定 然后b指向i下一个 c指向末尾

然后根据三者之间的和来收缩指针 这里为什么能够根据三者之和来收缩指针呢 因为我们的这个数组是带有信息的 也就是排序过的 这也就是为什么我们上面要先把数组排列然后再遍历

根据sum来判断两个指针如何来移动 如果sum<0 这个时候说明数小了 就把左边的指针往右移动 让它数值大一些

如果sum>0 说明数大了 就把右边的指针往左移动 让它数值小一些

如果=0 这个时候说明当前的i b c 就是我们想要寻找的三元组 我们就可以把它add进list 然后同时收缩两个指针 但是我们这个时候需要注意的是题目要求我们不能有重复的三元组 所以需要去重 这个时候我们就要去重 要对 i b c都要去重

对i用nums[i]==nums[i-1]来判断是否重复

注意这里为什么不能是nums[i]==nums[i+1]

因为left指针就是i+1 也就是i前面一位

如果用这个来判断的话就是来判断一个数组里面是否有重复的了

eg：

这个情况下 i 和left指向的就是相等的 但是这个是符合条件的 因为nums[i]==nums[i+1]这个本质就是用i和left指向的来做比较 但是i和left是可以进行比较的

所以只能用nums[i]==nums[i-1]

同理用nums[left]==nums[left-1]

和nums[right]==nums[right+1]

来进行去重 这里的right就是要去和右边的比了 因为左边 也就是right-1可能是left 但是left可以等于right

还可以对代码进行一个剪枝 也就是当i指向的元素都大于0的情况下 可以直接返回list数组了 因为left和right指向的都大于i指向的 这个时候后续移动三者不可能三者相加等于0 所以可以直接返回 这里根据排序之后和位置关系得出的条件是

nums[i]<=nums[left]<=nums[right]

if nums[i]>0

nums[i]+nums[left]+nums[right] !=0

所以直接返回之前找到的三元组即可

但是这里一定要注意的是返回不能写成 new Arraylist 因为这个返回的是一个空数组 没有返回到有数组的list

import 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 [] arr=new int[split.length]; for (int i = 0; i < split.length; i++) { arr[i]=Integer.parseInt(split[i]); } List<List<Integer>> lists = threeSum(arr); for (int i = 0; i < lists.size(); i++) { System.out.println(lists.get(i)); } } public static List<List<Integer>> threeSum(int[] nums) { //先对nums进行排序 Arrays.sort(nums); //然后在开始循环遍历nums ArrayList<List<Integer>> 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(i>0&&nums[i]==nums[i-1]){ continue; } //定义两个指针 放在后续数组的两段 int left=i+1; int right=nums.length-1; while(left<right){ int sum=nums[i]+nums[left]+nums[right]; if(sum==0){ list.add(Arrays.asList(nums[i],nums[left],nums[right])); //移动双指针 left++; right--; //对两个指针进行去重 while(left<right&&nums[left]==nums[left-1]){ left++; } while(left<right&&nums[right]==nums[right+1]){ right--; } }else if(sum>0){ right--; }else{ left++; } } } return list; } }

如果有什么问题可以评论区一起讨论一下 如果觉得写的还可以点个赞鼓励一下谢谢