1.盛最多水的容器题⽬链接11. 盛最多水的容器 - 力扣LeetCode问题描述算法原理解法⼀暴⼒求解算法思路枚举出能构成的所有容器找出其中容积最⼤的值。 容器容积的计算⽅式设两指针 i , j 分别指向⽔槽板的最左端以及最右端此时容器的宽度为 j - i 。由于容器的⾼度由两板中的短板决定因此可得容积公式 v (j - i) * min(height[i], height[j])class Solution { public: int maxArea(vectorint height) { int n height.size(); int ret 0; // 两层 for 枚举出所有可能出现的情况 for (int i 0; i n; i) { for (int j i 1; j n; j) { // 计算容积找出最⼤的那⼀个 ret max(ret, min(height[i], height[j]) * (j - i)); } } return ret; } };这种方法缺点就是会超时走不过去但解法没有错而且这是一个中档题出题人也不想让你就简简单单的暴力枚举就做出来的。解法⼆对撞指针算法思路设两个指针 left right 分别指向容器的左右两个端点此时容器的容积 :v (right - left) * min( height[right], height[left])容器的左边界为 height[left] 右边界为 height[right] 。为了⽅便叙述我们假设左边边界⼩于右边边界。如果此时我们固定⼀个边界改变另⼀个边界⽔的容积会有如下变化形式容器的宽度⼀定变⼩。由于左边界较⼩决定了⽔的⾼度。如果改变左边界新的⽔⾯⾼度不确定但是⼀定不会超过右边的柱⼦⾼度因此容器的容积可能会增⼤。如果改变右边界⽆论右边界移动到哪⾥新的⽔⾯的⾼度⼀定不会超过左边界也就是不会超过现在的⽔⾯⾼度但是由于容器的宽度减⼩因此容器的容积⼀定会变⼩的。由此可⻅左边界和其余边界的组合情况都可以舍去。所以我们可以 left 跳过这个边界继续去判断下⼀个左右边界。当我们不断重复上述过程每次都可以舍去⼤量不必要的枚举过程直到 left 与 right 相遇。期间产⽣的所有的容积⾥⾯的最⼤值就是最终答案。class Solution { public: int maxArea(vectorint height) { int left 0, right height.size() - 1, ret 0; while (left right) { int v min(height[left], height[right]) * (right - left); ret max(ret, v); // 移动指针 if (height[left] height[right]) left; else right--; } return ret; } };过程展现这道题的时间复杂度是O(n^2问题补充max(v)为什么不行max(v)这种写法在 C 中不合法因为max是一个函数在algorithm中需要至少两个参数来比较。好比max(3, 5)会返回 5但max(5)编译报错因为它不知道和谁比较可以不用ret而直接取所有v的最大值吗可以但必须事先存储所有v但这会浪费 O(n) 额外空间且没必要。2.有效三角形的个数题⽬链接611. 有效三角形的个数 - 力扣LeetCode问题描述算法原理解法⼀暴⼒求解会超时算法思路三层 for 循环枚举出所有的三元组并且判断是否能构成三⻆形。虽然说是暴⼒求解但是还是想优化⼀下判断三⻆形的优化如果能构成三⻆形需要满⾜任意两边之和要⼤于第三边。但是实际上只需让较⼩的两条边之和⼤于第三边即可。因此我们可以先将原数组排序然后从⼩到⼤枚举三元组⼀⽅⾯省去枚举的数量另⼀⽅⾯⽅便判断是否能构成三⻆形class Solution { public: int triangleNumber(vectorint nums) { // 1. 排序 sort(nums.begin(), nums.end()); int n nums.size(), ret 0; // 2. 从⼩到⼤枚举所有的三元组 for (int i 0; i n; i) { for (int j i 1; j n; j) { for (int k j 1; k n; k) { // 当最⼩的两个边之和⼤于第三边的时候统计答案 if (nums[i] nums[j] nums[k]) ret; } } } return ret; } };解法⼆排序 双指针用单调性使用双指针算法来解决问题先固定最大的数在最大的数的左区间内使用双指针算法快速统计出符合要求的三元组的个数算法思路先将数组排序。根据解法⼀中的优化思想我们可以固定⼀个最⻓边然后在⽐这条边⼩的有序数组中找出⼀个⼆元组使这个⼆元组之和⼤于这个最⻓边。由于数组是有序的我们可以利⽤对撞指针来优化。设最⻓边枚举到 i 位置区间 [left, right] 是 i 位置左边的区间也就是⽐它⼩的区间1.如果 nums[left] nums[right] nums[i] 说明 [left, right - 1] 区间上的所有元素均可以与 nums[right] 构成⽐nums[i] ⼤的⼆元组满⾜条件的有 right - left 种此时 right 位置的元素的所有情况相当于全部考虑完毕 right-- 进⼊下⼀轮判断2.如果 nums[left] nums[right] nums[i]说明 left 位置的元素是不可能与 [left 1, right] 位置上的元素构成满⾜条件的⼆元组left 位置的元素可以舍去 left 进⼊下轮循环class Solution { public: int triangleNumber(vectorint nums) { //优化 sort(nums.begin(),nums.end()); //利用双指针解决问题 int ret 0; int n nums.size(); for(int i n-1;i2;i--)//先固定最大的数 { //利用双指针快速统计符合二元数组的数 int left 0,right i-1; while(leftright) { if(nums[left]nums[right]nums[i]) { retright-left; right--; } else { left; } } } return ret; } };手写展现过程展现3.和为 s 的两个数字题⽬链接LCR 179. 查找总价格为目标值的两个商品 - 力扣LeetCode问题描述算法原理解法⼀暴⼒解法会超时算法思路两层 for 循环列出所有两个数字的组合判断是否等于⽬标值。算法流程两层 for 循环外层 for 循环依次枚举第⼀个数 a 内层 for 循环依次枚举第⼆个数 b 让它与 a 匹配注意细节我们挑选第⼆个数的时候可以不从第⼀个数开始选因为 a 前⾯的数我们都已经在之前考虑过了因此我们可以从 a 往后的数开始列举。然后将挑选的两个数相加判断是否符合⽬标值。class Solution { public: vectorint twoSum(vectorint price, int target) { int n price.size(); for (int i 0; i n; i) { // 第⼀层循环从前往后列举第⼀个数 for (int j i 1; j n; j) { // 第⼆层循环从 i 位置之后列举第⼆个 数 if (price[i] price[j] target) // 两个数的和等于⽬标值说明我们 已经找到结果了 return { price[i], price[j] }; } } return { -1, -1 }; } }解法⼆双指针 - 对撞指针算法思路注意到本题是升序的数组因此可以⽤对撞指针优化时间复杂度。算法流程a. 初始化 left right 分别指向数组的左右两端这⾥不是我们理解的指针⽽是数组的下标b. 当 left right 的时候⼀直循环1. 当 price[left] price[right] target 时说明找到结果记录结果并且返回2. 当 price[left] price[right] target 时对于 price[left] ⽽⾔此时 price[right] 相当于是 price[left] 能碰到的最⼤值别忘了这⾥是升序数组哈~。如果此时不符合要求说明在这个数组⾥⾯没有别的数符合 price[left] 的要求了最⼤的数都满⾜不了你你已经没救了。因此我们可以⼤胆舍去这个数让 left 去⽐较下⼀组数据那对于 price[right] ⽽⾔由于此时两数之和是⼩于⽬标值的 price[right]还可以选择⽐ price[left] ⼤的值继续努⼒达到⽬标值因此 right 指针我们按兵不动3.当 price[left] price[right] target 时同理我们可以舍去price[right] 最⼩的数都满⾜不了你你也没救了。接着让 right-- 继续⽐较下⼀组数据⽽ left 指针不变因为他还是可以去匹配⽐ price[right] 更⼩的数的class Solution { public: vectorint twoSum(vectorint price, int target) { int left 0, right price.size() - 1; while (left right) { int sum price[left] price[right]; if (sum target) right--; else if (sum target) left; else return { price[left], price[right] }; } // 照顾编译器 return { -4941, -1 }; } };手写分析过程展现问题补充问题1return {price[left], price[right]}是在初始化变量吗答return {price[left], price[right]};用的是初始化列表的语法但在return语句里它的身份是返回值不是变量初始化。这是在返回一个值不是初始化变量。编译器看到return {a, b}会根据函数返回类型自动转成vectorint{a, b}。问题2return {-4191, -1}里的数字是随便写的吗答是的。这只是占位用的因为函数声明了返回vectorint编译器要求所有执行路径都有返回值。正常情况下while循环内已经 return 了最后这个 return 不会执行到所以数字随便写。问题3return {}和return {a, b}有什么区别答return {}返回一个空vectorintreturn {a, b}返回一个有两个元素的vectorint值是 a 和 b4.三数之和题⽬链接15. 三数之和 - 力扣LeetCode题目描述算法原理算法思路本题与两数之和类似。与两数之和稍微不同的是题⽬中要求找到所有不重复的三元组。那我们可以利⽤在两数之和我们先固定一个数然后剩下的两个数之和变成它的相反数就可以和为0步骤如下1. 先排序2. 然后固定⼀个数 a 3. 在这个数后⾯的区间内使⽤双指针算法快速找到两个数之和等于 -a 即可。但是要注意的是这道题⾥⾯需要有去重操作找到⼀个结果之后 left 和 right 指针要跳过重复的元素当使⽤完⼀次双指针算法之后固定的 a 也要跳过重复的元素。class Solution { public: vectorvectorint threeSum(vectorint nums) { vectorvectorint ret; // 1. 排序 sort(nums.begin(), nums.end()); // 2. 利⽤双指针解决问题 int n nums.size(); for (int i 0; i n; ) // 固定数 a { if (nums[i] 0) break; // ⼩优化 int left i 1, right n - 1, target -nums[i]; while (left right) { int sum nums[left] nums[right]; if (sum target) right--; else if (sum target) left; else { ret.push_back({ nums[i], nums[left], nums[right] }); left, right--; // 去重操作 left 和 right while (left right nums[left] nums[left - 1]) left; while (left right nums[right] nums[right 1]) right--; } } // 去重 i i; while (i n nums[i] nums[i - 1]) i; } return ret; } };手写分析过程展示问题补充问题1ret.push_back({nums[i], nums[left], nums[right]})放进二维数组是的放进去的是二维数组的一行。ret的类型是vectorvectorint里面的每个元素都是vectorint{nums[i], nums[left], nums[right]}用初始化列表构造了一个一维vectorint里面有 3 个数push_back把这个一维vector塞进ret成为一行ret [ [a1, b1, c1], // 第一行一组三元组 [a2, b2, c2], // 第二行 [a3, b3, c3] // 第三行 ]那如果ret是vectorint一维push_back({1,2,3})能放进去吗不能会报错。因为vectorint的push_back只接受一个int不接受 3 个数。问题2i去重的时候i往后移了left和right不会没位置吗不会因为每次i移动后left和right会重新初始化每次i变化后进入下一轮循环left和right都会重新赋值不会出现没位置的问题。5.四数之和题⽬链接18. 四数之和 - 力扣LeetCode题目描述算法原理解法排序 双指针算法思路a. 依次固定⼀个数 a b. 在这个数 a 的后⾯区间上利⽤三数之和找到三个数使这三个数的和等于 target- a 即可。class Solution { public: vectorvectorint fourSum(vectorint nums, int target) { vectorvectorint ret; // 1. 排序 sort(nums.begin(), nums.end()); // 2. 利⽤双指针解决问题 int n nums.size(); for (int i 0; i n; ) // 固定数 a { // 利⽤ 三数之和 for (int j i 1; j n; ) // 固定数 b { // 双指针 int left j 1, right n - 1; long long aim (long long)target - nums[i] - nums[j]; while (left right) { int sum nums[left] nums[right]; if (sum aim) left; else if (sum aim) right--; else { ret.push_back({ nums[i], nums[j], nums[left], nums[right--] }); // 去重⼀ while (left right nums[left] nums[left - 1]) left; while (left right nums[right] nums[right 1]) right--; } } // 去重⼆ j; while (j n nums[j] nums[j - 1]) j; } // 去重三 i; while (i n nums[i] nums[i - 1]) i; } return ret; } };过程展现手写分析我们会发现这里面的后四道题都有一个操作那就是排序升序排序或者降序排序其实就是用到了双指针的单调性。这个方法很高效时间复杂度比暴力求解好的多但就是难想今天给大家介绍了后面遇到这种问题可以多了一种解题思路。第一个专题双指针就已经结束下一个专题滑动窗口