笔试算法 - 双指针篇（二）：四大经典求和题型 + 有效三角形计数问题

目录前言一、有效三角形的个数二、查找总价值为目标值的两个商品三、三数之和四、四数之和结语 云泽Q个人主页 专栏传送入口: 《C语言》《数据结构》《C》《Linux》《蓝桥杯系列》《笔试算法》⛺️遇见安然遇见你不负代码不负卿~前言大家好啊我是云泽Q欢迎阅读我的文章一名热爱计算机技术的在校大学生喜欢在课余时间做一些计算机技术的总结性文章希望我的文章能为你解答困惑~一、有效三角形的个数611.有效三角形的个数解法一暴力求解会超时算法思路三层 for 循环枚举出所有的三元组并且判断是否能构成三角形。虽然说是暴力求解但是还是想优化一下判断三角形的优化如果能构成三角形需要满足任意两边之和要大于第三边。但是实际上只需让较小的两条边之和大于第三边即可。因此我们可以先将原数组排序然后从小到大枚举三元组一方面省去枚举的数量另一方面方便判断是否能构成三角形。解法二排序 双指针算法思路先将数组排序。根据「解法一」中的优化思想我们可以固定一个「最长边」然后在比这条边小的有序数组中找出一个二元组使这个二元组之和大于这个最长边。由于数组是有序的我们可以利用「对撞指针」来优化。设最长边枚举到 i 位置区间 [left, right] 是 i 位置左边的区间也就是比它小的区间如果 nums[left] nums[right] nums[i]说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成比 nums[i] 大的二元组满足条件的有 right - left 种此时 right 位置的元素的所有情况相当于全部考虑完毕right减减进入下一轮判断如果 nums[left] nums[right] nums[i]说明 left 位置的元素是不可能与 [left 1, right] 位置上的元素构成满足条件的二元组left 位置的元素可以舍去left 进入下轮循环classSolution{public:inttriangleNumber(vectorintnums){sort(nums.begin(),nums.end());intnnums.size();intret0;for(intcurn-1;cur2;cur--){//left 和 right要初始化在循环内部left和right的位置是随cur的位置动态变化的intleft0,rightcur-1;while(leftright){if(nums[left]nums[right]nums[cur]){retright-left;right--;}else{left;}}}returnret;}};二、查找总价值为目标值的两个商品LCR 179.查找总价值为目标值的两个商品该题目就不写题解了因为确实比较简单若是你把前一篇文章的题目笔试算法 - 双指针篇一移动零、复写零、快乐数与盛水容器都自己好好写过的话我相信你大概率是能自己做出来这道题目的classSolution{public:vectorinttwoSum(vectorintprice,inttarget){intnprice.size();intleft0,rightn-1;while(leftright){intsumprice[left]price[right];if(sumtarget)right--;elseif(sumtarget)left;elsereturn{price[left],price[right]};}//过编译器的语法检测在该题目中并无此种结果return{-1,-1};}};三、三数之和LeetCode 15. 三数之和解法排序 双指针算法思路本题与两数之和类似是非常经典的面试题。与两数之和稍微不同的是题目中要求找到所有「不重复」的三元组。那我们可以利用在两数之和那里用的双指针思想来对我们的暴力枚举做优化i. 先排序ii. 然后固定一个数 aiii. 在这个数后面的区间内使用「双指针算法」快速找到两个数之和等于 −a 即可。但是要注意的是这道题里面需要有「去重」操作i. 找到一个结果之后left 和 right 指针要「跳过重复」的元素ii. 当使用完一次双指针算法之后固定的 a 也要「跳过重复」的元素。classSolution{public:vectorvectorintthreeSum(vectorintnums){vectorvectorintret;//排序sort(nums.begin(),nums.end());//利用双指针解决问题intnnums.size();for(inti0;in;){if(nums[i]0)break;//小优化intlefti1,rightn-1,target-nums[i];while(leftright){intsumnums[left]nums[right];if(sumtarget)right--;elseif(sumtarget)left;else{ret.push_back({nums[i],nums[left],nums[right]});//不漏left,right--;//对 left 和 right 去重 避免越界while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])right--;}}//对 i 去重 避免越界i;while(innums[i]nums[i-1])i;}returnret;}};这是一种对 i 去重 避免越界还有另外一种写法classSolution{public:vectorvectorintthreeSum(vectorintnums){vectorvectorintret;//排序sort(nums.begin(),nums.end());//利用双指针解决问题intnnums.size();for(inti0;in;i){if(nums[i]0)break;//小优化intlefti1,rightn-1,target-nums[i];while(leftright){intsumnums[left]nums[right];if(sumtarget)right--;elseif(sumtarget)left;else{ret.push_back({nums[i],nums[left],nums[right]});//不漏left,right--;//对 left 和 right 去重 避免越界while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])right--;}}//对 i 去重 避免越界while(i1nnums[i1]nums[i])i;}returnret;}};我个人还是更喜欢第二种写法for循环少写一个逻辑看着有点难受按照你的代码风格来写就行了但是千万要注意第二种写法不能写为while(i n nums[i 1] nums[i]) i;这里nums[i 1]是会触发越界访问的因为有这种情况外层for(int i0; in; i);进入循环体时i 一定满足 0 ≤ i ≤ n-1i 永远合法当 i n-1最后一个元素数组最大合法下标左边条件i n → n-1 n →结果为 true短路失效程序会立刻执行右边nums[i1] → nums[n]数组下标范围是0~n-1访问nums[n] →直接越界非法访问程序崩溃 / 报错举个直接触发越界的测试用例nums{-2,-1,-1};// 排序后不变n3数组全负数触发不了nums[i]0 break优化循环 i 会依次走到 0、1、2i2 就是 n-12执行while(in nums[i1]nums[i])i23 成立直接访问 nums [3] → 越界还可以再优化一个点因为三数之和需要凑 3 个数字取a这个数字的时候当数组全为负数和0的时候i最多也只能指向 n - 3的位置这样就是极致优化了classSolution{public:vectorvectorintthreeSum(vectorintnums){vectorvectorintret;//排序sort(nums.begin(),nums.end());//利用双指针解决问题intnnums.size();for(inti0;in-2;i){if(nums[i]0)break;//小优化intlefti1,rightn-1,target-nums[i];while(leftright){intsumnums[left]nums[right];if(sumtarget)right--;elseif(sumtarget)left;else{ret.push_back({nums[i],nums[left],nums[right]});//不漏left,right--;//对 left 和 right 去重 避免越界while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])right--;}}//对 i 去重 避免越界while(i1nnums[i1]nums[i])i;}returnret;}};这是使用了哈希表的解法我个人认为看一看知道这个思路可以举一反三即可自然是双指针更优的classSolution{public:vectorvectorintthreeSum(vectorintnums){vectorvectorintret;sort(nums.begin(),nums.end());// 代码排序保留intnnums.size();for(inti0;in-2;i)// 代码固定第一个数i保留{if(nums[i]0)break;// 代码优化保留inttarget-nums[i];// 代码要找的两数之和target保留// 哈希核心代码重点讲解 unordered_setinthash;// 1. 创建一个空哈希表用来存「已经遍历过的数字」// 2. 遍历i后面的所有数j相当于双指针的遍历for(intji1;jn;j){// 3. 计算需要找的第三个数字 need// 公式need nums[j] target → need target - nums[j]// 最终三数和nums[i] need nums[j] 0intneedtarget-nums[j];// 4. 关键用count查need在不在哈希表里if(hash.count(need)){// 找到了need是之前遍历过的数凑成三元组ret.push_back({nums[i],need,nums[j]});// 5. 去重跳过重复的j避免输出重复结果while(j1nnums[j]nums[j1])j;}// 6. 把当前nums[j]放进哈希表给后面的j用hash.insert(nums[j]);}// while(i1nnums[i1]nums[i])i;// 你的代码i去重保留}returnret;}};其实我个人觉得这道题目完全可以算得上是困难题目了力扣上的题目难度划分还是不太严谨四、四数之和LeetCode 18.四数之和classSolution{public:vectorvectorintfourSum(vectorintnums,inttarget){vectorvectorintret;//排序sort(nums.begin(),nums.end());intnnums.size();//查找四元组for(inti0;in-3;i)//固定a{for(intji1;jn-2;j)//固定b{intleftj1,rightn-1;longlongaim(longlong)target-nums[i]-nums[j];while(leftright){longlongsum(longlong)nums[left]nums[right];if(sumaim)right--;elseif(sumaim)left;else{ret.push_back({nums[i],nums[j],nums[left],nums[right]});left,right--;//去重while(leftrightnums[left]nums[left-1])left;while(leftrightnums[right]nums[right1])right--;}}//去重jwhile(j1nnums[j1]nums[j])j;}//去重iwhile(i1nnums[i1]nums[i])i;}returnret;}};解法排序 双指针算法思路a. 依次固定一个数 ab. 在这个数 a 的后面区间上利用「三数之和」找到三个数使这三个数的和等于 target−a 即可。这里还有一个要注意的点C 算术运算规则只要有一个操作数是 long long所有数会自动提升为 long long 计算结果也是 long long→ 不需要给每一个变量都加 (long long)结语