【C】优选算法必修篇之双指针实战有效三角形个数 和为s的两个数字双指针应用场景目录1. 有效三角形个数1.1 题目链接1.2 题目描述1.3 题目示例1.4 算法思路1.5 核心代码1.6 示例测试总代码2. 和为s的两个数字2.1 题目链接2.2 题目描述2.3 题目示例2.4 算法思路2.5 核心代码2.6 示例测试总代码总结双指针应用场景应用场景介绍--------------------链接直达请点击目录1. 有效三角形个数1.1 题目链接题目链接直达----------请点击1.2 题目描述1.3 题目示例1.4 算法思路我们首先得清除构成三角形的条件两边之和大于第三边两边之差小于第三边但是要验证这两个条件好像很麻烦有没有更简单的方法呢当三个数abc我们从小到大排序然后你会发现只需要满足a b c就能构成一个有效的三角形。在排序后的数组中我们固定最大的边nums[k]作为三角形的第三边然后在[0, k-1]范围内使用对撞指针寻找满足条件的两边。具体来说设置left 0和right k-1。当nums[left] nums[right] nums[k]时由于数组是升序排列left到right-1的所有位置与当前right组成的配对都能满足条件。这时我们可以直接给计数器增加right - left个有效组合然后将right左移一位。如果nums[left] nums[right] nums[k]说明当前的两边之和太小需要增大其中一边。由于right已经是当前范围内较大的值我们通过将left右移来增加两边之和。1.5 核心代码#includeiostream#includevector#includealgorithmusingnamespacestd;classSolution{public:inttriangleNumber(vectorintnums){sort(nums.begin(),nums.end());//升序排序intnnums.size();//n为数组大小intret0;for(intin-1;i2;i--)//因为最少三条边所以i2{intleft0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]){retright-left;right--;}else{left;}}}returnret;}};1.6 示例测试总代码#includeiostream#includevector#includealgorithmusingnamespacestd;classSolution{public:inttriangleNumber(vectorintnums){sort(nums.begin(),nums.end());//升序排序intnnums.size();//n为数组大小intret0;for(intin-1;i2;i--)//因为最少三条边所以i2{intleft0,righti-1;while(leftright){if(nums[left]nums[right]nums[i]){retright-left;right--;}else{left;}}}returnret;}};intmain(){vectorintnums1{4,2,3,4};coutSolution().triangleNumber(nums1)endl;return0;}2. 和为s的两个数字2.1 题目链接题目链接直达----------请点击2.2 题目描述2.3 题目示例2.4 算法思路因为这个数组题目中已经说明是升序了我们可以同样可以采用对撞指针来实现。一个指向第一个数据一个指向最后一个数据然后让他们相加。如果结果大于traget说明过大right–如果结果小于traget说明太小left如果相等就返回直到left和right指向同一个位置循环停止。2.5 核心代码//有效三角形个数和为s的两个数字#includeiostream#includevectorusingnamespacestd;classSolution{public:vectorinttwoSum(vectorintprice,inttarget){intleft0;intrightprice.size()-1;while(leftright){if(price[left]price[right]target){right--;}elseif(price[left]price[right]target){left;}else{return{price[left],price[right]};//等价于vectorint ans;//ans.push_back(price[left]);//ans.push_back(price[right]);//return ans;}}return{-1,-1};}};2.6 示例测试总代码//有效三角形个数和为s的两个数字#includeiostream#includevector#includealgorithmusingnamespacestd;classSolution{public:vectorinttwoSum(vectorintprice,inttarget){intleft0;intrightprice.size()-1;while(leftright){if(price[left]price[right]target){right--;}elseif(price[left]price[right]target){left;}else{return{price[left],price[right]};//等价于vectorint ans;//ans.push_back(price[left]);//ans.push_back(price[right]);//return ans;}}return{-1,-1};}};intmain(){vectorintnums1{3,9,12,15};vectorintresultSolution().twoSum(nums1,18);// 正确输出vector的方式cout[;for(inti0;iresult.size();i){coutresult[i];if(iresult.size()-1){cout,;}}cout]endl;return0;}总结在掌握了双指针基础模型快慢指针、对撞指针之后我们进一步探索双指针在数学组合问题中的精妙应用。本篇通过「有效三角形个数」和「和为s的两个数字」两个经典问题。掌握了这些基础模型后我们可以进一步挑战三数之和—— 在二维对撞基础上增加一维遍历处理更复杂的组合约束四数之和—— 双层循环对撞指针的组合应用展现分治思想的威力最接近的三数之和—— 引入差值最小化的优化目标拓展双指针的适用边界这些进阶问题都建立在本文所述的核心思想之上——排序预处理 指针智能移动体现了算法设计中分而治之的经典智慧。下一篇我们将深入探索多指针的高阶应用【C】优选算法必修篇之双指针实战三数之和 四数之和