算法专题笔记------三数之和与四数之和题目描述给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target你可以按 任意顺序 返回答案 。示例 1输入nums [1,0,-1,0,-2,2], target 0输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2输入nums [2,2,2,2,2], target 8输出[[2,2,2,2]]力扣题目链接三数之和要想做出四数之和我们必须先彻底搞懂三数之和这道题目他是我们做四数之和的基础二者解法一脉相承三数之和力扣链接暴力解法这种解法很容易想到 就是用三层for来遍历 穷举出所有三元组for(inti0;inums.length;i){for(intji1;jnums.length;j){for(intkj1;knums.length;k){if(nums[i]nums[j]nums[k]0){//将结果放入结果集}}}}return//结果集暴力解法的时间复杂度是O(N^3)双指针解法在暴力解法中我们只是一味地遍历数组但是其实有可能在第一层就可以给结果宣判死刑了这样就可以省去很多没必要的操作因为暴力解法的时间复杂度已经飙到O(N^3)了所以我们可以考虑先给数组排个序排序操作的复杂度只有O(N*logN)来方便后续双指针操作双指针核心思想简单来说就是定一动二既然结果是三元组那么我们就先定死一个数然后再用剩下两个数去凑结果即可。对定一个数的代码实现很简单就是for循环的的循环索引对于“动二”操作就是双指针了,至于凑结果一会结合下面的代码讲解可以先粗略浏览一下下面的代码片段int[]nums{-2,-1,0,1,2};//for循环负责 “ 定一 ”for(inti0;inums.length;i){intlefti1;intrightnums.length-1;//while循环负责 “ 动二 ”while(leftright){intsumnums[i]nums[left]nums[right];//下面的 if--else 负责 “ 凑结果 ”if(sum0){right--;}elseif(sum0){left;}else{//将结果记录下来 { nums[i], nums[left], nums[right] }right--;left;}}}相信看完上面的代码你能很清楚的看出来所谓的定一与动二是通过哪些语句操作的了现在的主要问题是让指针这么移动的逻辑是什么。首先执行for循环的时候索引首先确定了sum变量的第一项以及left的位置然后我们操作双指针的区间就确定为left~数组末尾然后再看if--else结构是如何移动双指针的事先要先明确的是数组是从小到大排好序的结果大了(sum0)right左移nums[right]变小 》sum减小结果小了(sum0)left右移nums[left]变大 》sum变大找到目标三元组(sum0)再让指针移动一次不然会死循环小细节while的执行条件不能是因为当left right时结果就只剩两个数了经过上面的操作我们就能找到一组包含i索引的全部结果了再进行for就能找齐所有结果去重操作上面的解法对于数组{-2,-1,0,1,2}是成立的但是如果我把数组改为{-1,-1,0,1,2}那么输出就变成了[ [-1,-1,2], [-1,0,1], [-1,0,1] ]了很明显有一组出现重复了这是为什么呢再看我们记录的解的形式{ nums[i], nums[left], nums[right] }因为当i 0 和 i 1时nums[i]都是 -1所以就出现了重复结果为了解决这个问题我们就想能不能让 i 直接跳到下一个和当前不同的值呢至此数组的排序又发挥了巨大的作用所有相同的值都挨在一起所以可以写出代码if(i0nums[i]nums[i-1]){continue;//值相同时就掠过当前索引}我们又向胜利迈进了一步可是力扣刁钻的测试还在追杀我们再改一下数组{-20002222}输出[ [-2, 0, 2], [-2, 0, 2], [-2, 0, 2] ]又重复了哈哈不过这难不倒聪明的鼠鼠类比对索引i的去重 很容易写出对left和right的去重代码while(leftrightnums[left]nusm[left1]){left;}while(leftrightnums[right]nums[right-1]){right--;}至此去重操作全部完成了剪枝操作轻舟已过万重山剪枝操作可以进一步加快代码的运行效率sum的目标值是0那如果我们的索引i已经是一个大于0的数了数组又是升序那以后的值是不是就一定不行了呢是的所以剪枝代码如下if(nums[i]0){returnret;}现在我们拿下了力扣通过率仅有40.3%的三数之和接下来可以趁着手感火热一起秒掉通过率36.9%的四数之和四数之和sum nums[i] nums[j] nums[left] nums[right]众所周知4 3 1所以 四数之和 等于一数 三数之和回忆一下刚才的三数之和我们输出了什么是不是一组令sum 0的三元组啊那么现在只要找到令sum 负的第一个数的三元组就能拼接成本题的答案了那怎么找第一个数呢是不是在来一个for就可以了下面鼠鼠快速的带大家啊过一遍逻辑暴力解法四层forO(N^4)双指针解法双指针核心思想这里只需要将原来的sum是否大于零改为是否大于负的第一个数即可,并由定一动二改为定二ij动二leftright去重操作这里要注意去重操作是从第二个位置开始的在三数之和中i 0因为零是第一个位置if(i0/*零是第一个位置*/nums[i]nums[i-1]){continue;//值相同时就掠过当前索引}写四数之和时我们的第二格数也就是j是从i 1开始取的所以要写j i 1剪枝操作这里你可能会想我要如何剪枝呢三数之和的时候很简单只要第一个数大了那剩下的就不用看了。但是现在目标不是0了目标是自定义的target变量还能剪枝吗当然能结果肯定越加越大啊那只要nums[i]target我就剪枝。错了看下面数组{-5,-4,-1, 1, 3, 8}, target -10-5-10但是如果剪枝就会错过正确答案那什么时候剪枝呢是不是从i3即nums[i] 1时就可以了。所以对i剪枝逻辑如下if(nums[i]target(nums[i]0||target0)){returnret;}解决了如何剪枝还要解决对谁剪枝既然i可以剪枝那么j是不是也可以剪枝呢是的 还记得定二动二吗只要是定的就可以剪枝剪枝的核心逻辑就是一旦可以通过定下来的变量排除结果那动的变量就没必要动了总结这两道题的价值所在就是双指针去重剪枝与此同时对代码的边界处理也有很高的要求鼠鼠刷这道题的时候也是一遍遍的调试代码才AC的。所以写这篇博客希望帮助到也在刷这道题的兄弟。最后再把可以通过的Java代码贴出来吧我没有对j进行剪枝大家可以补充这部分代码片段到评论区哟classSolution{publicListListIntegerfourSum(int[]nums,inttarget){ListListIntegerretnewArrayList();Arrays.sort(nums);for(inti0;inums.length;i){if(nums[i]target(nums[i]0||target0)){returnret;}if(i0nums[i]nums[i-1]){continue;}intleft;intright;intji1;for(;jnums.length;j){if(ji1nums[j]nums[j-1]){continue;}leftj1;rightnums.length-1;while(leftright){if(nums[j]nums[left]nums[right]nums[i]target){left;}elseif(nums[j]nums[left]nums[right]nums[i]target){right--;}else{ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(leftrightnums[left]nums[left1]){left;}while(leftrightnums[right]nums[right-1]){right--;}right--;left;}}}}returnret;}}
算法专题笔记------一篇讲明白 LeetCode三数之和与四数之和
算法专题笔记------三数之和与四数之和题目描述给你一个由 n 个整数组成的数组 nums 和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] 若两个四元组元素一一对应则认为两个四元组重复0 a, b, c, d na、b、c 和 d 互不相同nums[a] nums[b] nums[c] nums[d] target你可以按 任意顺序 返回答案 。示例 1输入nums [1,0,-1,0,-2,2], target 0输出[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]示例 2输入nums [2,2,2,2,2], target 8输出[[2,2,2,2]]力扣题目链接三数之和要想做出四数之和我们必须先彻底搞懂三数之和这道题目他是我们做四数之和的基础二者解法一脉相承三数之和力扣链接暴力解法这种解法很容易想到 就是用三层for来遍历 穷举出所有三元组for(inti0;inums.length;i){for(intji1;jnums.length;j){for(intkj1;knums.length;k){if(nums[i]nums[j]nums[k]0){//将结果放入结果集}}}}return//结果集暴力解法的时间复杂度是O(N^3)双指针解法在暴力解法中我们只是一味地遍历数组但是其实有可能在第一层就可以给结果宣判死刑了这样就可以省去很多没必要的操作因为暴力解法的时间复杂度已经飙到O(N^3)了所以我们可以考虑先给数组排个序排序操作的复杂度只有O(N*logN)来方便后续双指针操作双指针核心思想简单来说就是定一动二既然结果是三元组那么我们就先定死一个数然后再用剩下两个数去凑结果即可。对定一个数的代码实现很简单就是for循环的的循环索引对于“动二”操作就是双指针了,至于凑结果一会结合下面的代码讲解可以先粗略浏览一下下面的代码片段int[]nums{-2,-1,0,1,2};//for循环负责 “ 定一 ”for(inti0;inums.length;i){intlefti1;intrightnums.length-1;//while循环负责 “ 动二 ”while(leftright){intsumnums[i]nums[left]nums[right];//下面的 if--else 负责 “ 凑结果 ”if(sum0){right--;}elseif(sum0){left;}else{//将结果记录下来 { nums[i], nums[left], nums[right] }right--;left;}}}相信看完上面的代码你能很清楚的看出来所谓的定一与动二是通过哪些语句操作的了现在的主要问题是让指针这么移动的逻辑是什么。首先执行for循环的时候索引首先确定了sum变量的第一项以及left的位置然后我们操作双指针的区间就确定为left~数组末尾然后再看if--else结构是如何移动双指针的事先要先明确的是数组是从小到大排好序的结果大了(sum0)right左移nums[right]变小 》sum减小结果小了(sum0)left右移nums[left]变大 》sum变大找到目标三元组(sum0)再让指针移动一次不然会死循环小细节while的执行条件不能是因为当left right时结果就只剩两个数了经过上面的操作我们就能找到一组包含i索引的全部结果了再进行for就能找齐所有结果去重操作上面的解法对于数组{-2,-1,0,1,2}是成立的但是如果我把数组改为{-1,-1,0,1,2}那么输出就变成了[ [-1,-1,2], [-1,0,1], [-1,0,1] ]了很明显有一组出现重复了这是为什么呢再看我们记录的解的形式{ nums[i], nums[left], nums[right] }因为当i 0 和 i 1时nums[i]都是 -1所以就出现了重复结果为了解决这个问题我们就想能不能让 i 直接跳到下一个和当前不同的值呢至此数组的排序又发挥了巨大的作用所有相同的值都挨在一起所以可以写出代码if(i0nums[i]nums[i-1]){continue;//值相同时就掠过当前索引}我们又向胜利迈进了一步可是力扣刁钻的测试还在追杀我们再改一下数组{-20002222}输出[ [-2, 0, 2], [-2, 0, 2], [-2, 0, 2] ]又重复了哈哈不过这难不倒聪明的鼠鼠类比对索引i的去重 很容易写出对left和right的去重代码while(leftrightnums[left]nusm[left1]){left;}while(leftrightnums[right]nums[right-1]){right--;}至此去重操作全部完成了剪枝操作轻舟已过万重山剪枝操作可以进一步加快代码的运行效率sum的目标值是0那如果我们的索引i已经是一个大于0的数了数组又是升序那以后的值是不是就一定不行了呢是的所以剪枝代码如下if(nums[i]0){returnret;}现在我们拿下了力扣通过率仅有40.3%的三数之和接下来可以趁着手感火热一起秒掉通过率36.9%的四数之和四数之和sum nums[i] nums[j] nums[left] nums[right]众所周知4 3 1所以 四数之和 等于一数 三数之和回忆一下刚才的三数之和我们输出了什么是不是一组令sum 0的三元组啊那么现在只要找到令sum 负的第一个数的三元组就能拼接成本题的答案了那怎么找第一个数呢是不是在来一个for就可以了下面鼠鼠快速的带大家啊过一遍逻辑暴力解法四层forO(N^4)双指针解法双指针核心思想这里只需要将原来的sum是否大于零改为是否大于负的第一个数即可,并由定一动二改为定二ij动二leftright去重操作这里要注意去重操作是从第二个位置开始的在三数之和中i 0因为零是第一个位置if(i0/*零是第一个位置*/nums[i]nums[i-1]){continue;//值相同时就掠过当前索引}写四数之和时我们的第二格数也就是j是从i 1开始取的所以要写j i 1剪枝操作这里你可能会想我要如何剪枝呢三数之和的时候很简单只要第一个数大了那剩下的就不用看了。但是现在目标不是0了目标是自定义的target变量还能剪枝吗当然能结果肯定越加越大啊那只要nums[i]target我就剪枝。错了看下面数组{-5,-4,-1, 1, 3, 8}, target -10-5-10但是如果剪枝就会错过正确答案那什么时候剪枝呢是不是从i3即nums[i] 1时就可以了。所以对i剪枝逻辑如下if(nums[i]target(nums[i]0||target0)){returnret;}解决了如何剪枝还要解决对谁剪枝既然i可以剪枝那么j是不是也可以剪枝呢是的 还记得定二动二吗只要是定的就可以剪枝剪枝的核心逻辑就是一旦可以通过定下来的变量排除结果那动的变量就没必要动了总结这两道题的价值所在就是双指针去重剪枝与此同时对代码的边界处理也有很高的要求鼠鼠刷这道题的时候也是一遍遍的调试代码才AC的。所以写这篇博客希望帮助到也在刷这道题的兄弟。最后再把可以通过的Java代码贴出来吧我没有对j进行剪枝大家可以补充这部分代码片段到评论区哟classSolution{publicListListIntegerfourSum(int[]nums,inttarget){ListListIntegerretnewArrayList();Arrays.sort(nums);for(inti0;inums.length;i){if(nums[i]target(nums[i]0||target0)){returnret;}if(i0nums[i]nums[i-1]){continue;}intleft;intright;intji1;for(;jnums.length;j){if(ji1nums[j]nums[j-1]){continue;}leftj1;rightnums.length-1;while(leftright){if(nums[j]nums[left]nums[right]nums[i]target){left;}elseif(nums[j]nums[left]nums[right]nums[i]target){right--;}else{ret.add(Arrays.asList(nums[i],nums[j],nums[left],nums[right]));while(leftrightnums[left]nums[left1]){left;}while(leftrightnums[right]nums[right-1]){right--;}right--;left;}}}}returnret;}}
