初识算法 · 双指针(2)
目录
前言：
本文介绍两个题目，盛最多水的容器和有效三角形的个数，对应的Leetcode的题目链接为：
介绍这两个题目，会从两角度进行介绍，暴力解法以及算法，整个题目的讲解分为三个部分，题目解析，算法原理，算法编写三个部分进行讲解。
现在就进入正题吧！
盛最多水的容器
题目解析：
题目：
题目实例：
该题目的要求是找到最大的值，值的求法为下标相减 * 两数中小的那个数，那么我们可以不管三七二十一，直接暴力，即将所有的值都给求出来，自然是两个循环就可以解决了，伪代码为：
for(...)
{
//确定左边的边长
for(...)
{
//确定右边的边长
}
}
虽然说最后求值部分是一个等差数列的求和方式，但是不影响，最终的时间复杂度依旧是O(N^2)
对于为什么求值是*两数中较小的那个数，木桶效应相信大家都是听说过的：
即一个木桶盛水的容量不是取决于最长的木板，而是最短的那个木板，所以求值的时候是最小的那个值。
算法原理：
在算法原理部分，我们已经在上文了解了暴力解法，所以不再赘述暴力解法，这里是找两个数，保证下标相减 * 最小的那个数是最大值，那么找两个数，我们不妨使用双指针来解决。
容量大小 = 两数中的较小值 * 下标之差
我们不妨规定左指针从0开始，右指针从size - 1开始，如果我们从同向的方向进行判断，那么就会存在两变量，下标之差可能增大可能减少，较小值不确定，就会有4种情况，是比较难控制的，如果是我们定向的让右指针从右边开始，即数组的最末端，随着右指针往左或者是左指针往右，都是下标之差减少的过程，那么我们为了找最大值，需要保证的就是两个数之间的规则了。
谁小谁就移动，并且我们需要记录移动之前的容量大小，记录之后，需要比较移动之后的容量大小。我们取最大的即可。
算法编写：
class Solution { public: int maxArea(vector<int>& height) { int left = 0, right = height.size() - 1; int ret = 0,ans = 0; while(right > left) { ret = min(height[left],height[right]) * (right - left); ans = max(ret,ans); if(height[left] > height[right]) right--; else left++; } return ans; } };此时就完美通过了。
有效三角形的个数
题目解析：
题目：
题目示例：
通过示例，我们可以得出来一个结论是：下标不同数值相同的元素我们可以使用，即便组成的三角形是一样的。根据题目要求，我们首先得到的一个信息是，我们需要通过判断获取到的三个元素是否能构成三角形，那么根据初中的理论，三角形的充要条件是：任意两边之和大于第三边。
难道我们判断三角形的时候，就都要写三个条件吗？那是不是有点太麻烦了？这点先不管，题目中还有的提示是数组是非负的整数数组，也就是不会出现非整数和负数，我们返回值是能构成三角形的个数。题目要求不多，解析到这里已经差不多了。
算法原理：
还是那句话，遇事不决先暴力。
这道题的暴力解法是很简单的，我们只需要三个循环，一个循环找一条边即可：
for() { for() { for() { //判断三角形是否成立 } } }但是时间复杂度也是惊人的高，达到了O(N^3)，一般leetcode上这种题，到最后几个样例的时候，O(N^3)一般都是会超时的。
所以我们需要另辟蹊径，那么就使用双指针算法，对于双指针来说，影响的是两个数，这是可是三个数，我们应该如何操作呢？
我们不妨借助单调性，如果借助单调性，我们碰见一组数，我们就要判断是否为三角形，这是否太麻烦了？那么有了单调性，比如a + b > c，随着指针往右边走，两个小的数都大于c了，其他的数还能不大于吗？到那个地步我们可以直接ans = 下标之差了，后面的肯定是符合条件的。那么c为最大边的所有三角形找到了，--即可。
算法编写：
class Solution { public: int triangleNumber(vector<int>& nums) { int ans = 0; sort(nums.begin(),nums.end()); for(int i = nums.size() - 1; i >= 2 ;i--) { int left = 0,right = i - 1; while(left < right) { if(nums[left] + nums[right] > nums[i]) ans += (right - left),right--; else left++; } } return ans; } };此时的时间复杂度为O(N^2)，相对于O(N^3)，是一个非常大的提升。
以上就是两道算法题目的详解。
感谢阅读！
