我和双指针的初次亲密邂逅：那一刻心跳加速

1. 盛最多水的容器

题目传送门

1.1 题目说明

给定一个长度为 n 的整数数组 height。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i])。

找出其中的两条垂线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大值。

说明：你不能倾斜容器。

示例 1

输入：[1,8,6,2,5,4,8,3,7] 输出：49 解释：图中的垂线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

示例 2

输入：height = [1,1] 输出：1

1.2 题目分析

暴力枚举，将所有的情况计算出来，两个for循环

但是这个是会超时的，时间复杂度是O(N^2)

所以我们使用双指针进行解决

利用单调性，使用双指针来解决问题，遍历一遍数组我们就能解决问题了，时间复杂度是O(N)

一个指针指向最左边，一个指向最右边

我们先算出来一个体积v

这两个指针向内活动

根据两个指针指向的数据的大小进行比较，谁小谁就进行移动，然后更新我们的体积最大值，直到这两个指针重叠 定义两个指针，一左一右

我们移动双指针，向内进行移动

每次移动之前计算当前的体积

然后更新最大值

每次两个指针中最小的进行一个移动操作

1.3代码部分

class Solution {
public:
    int maxArea(vector<int>& 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--;
            }
        }
        //出了循环之后，ret就存放着所有的体积中的最大的值
        return ret;
    }
};

1.4 代码解析

我们先创建两个指针，左指针指向0，右指针指向n-1，n是数组的元素的个数，n-1是这个数组中最后一个数字的下标

我们利用循环进行这个数组的遍历操作 遍历的条件就是left不能超过right 我们进行体积的计算 以及就是这个底乘高 底是right-left 高就是我们左右指针所对应的爱那个数字中的最小的那个 高：min(height[left],height[right]) 然后我们的体积就计算好了 然后我们每次对体积进行一个更新的操作 因为我们的两个指针一直在运动 我们每次更新出最大的体积 所以我们使用max()来进行操作 如果我们的左指针对应的高度小于右指针对应的高度的话，我们让左指针往右边挪动一位。如果左指针对应的高度大的话，我们让右指针往左边挪动一位

出了循环之后，我们的ret里面就存放着最大的体积了 我们直接进行返回操作就行了

2.有效三角形的个数

题目传送门

2.1 题目说明

给定一个包含非负整数的数组 nums，返回其中可以组成三角形三条边的三元组个数。

示例 1

• 输入：nums = [2, 2, 3, 4]
• 输出：3
• 解释：有效的三角形组合是：
  1. 2, 3, 4 （使用第一个 2）
  2. 2, 3, 4 （使用第二个 2）
  3. 2, 2, 3

示例 2

• 输入：nums = [4, 2, 3, 4]
• 输出：4

注意点：三个边长需要满足三角形的基本不等式：任意两边之和大于第三边。

2.2 题目分析

判断策略一：三角形构成的知识：任意两个边的和大于第三个边，但是这个是需要判断三次的

判断策略二：如果我们直到这三个数的大小顺序的话，我们只需要将最小的两个数进行相加和最大的数进行比较，但是前提我们需要进行一个排序的操作

解法一：

时间复杂度就是O(N^3)

如果我们选择这个第一种策略的话我们的时间复杂度就是3O(N^3)

如果是第二种的策略的话，我们排序的时间复杂度是NlogN

然后所有总的时间复杂度是NlogN+ O(N^3)

3O(N^3)>NlogN+ O(N^3)

所以我们是不选择这个暴力枚举的方法的

解法二： 利用单调性，使用双指针算法来解决问题

在这里插入图片描述

我们先判断左指针和右指针的和与C进行一个相加的操作

如果大于C 的话，并且这个数组是已经排好了序的，所以在a和b这个区间之内，随便挑出了一个数来替换a和b进行相加都大于c的，那么我们就也不需要傻傻的往中间相加并且进行比较的操作了

所以如果我们进行一个计算之后发现左右指针相加大于最后的数的话，那么我们就直接能找到right-left种情况，因为中间的数都比a大，所以有right-left种情况

如果b=9这个情况判断完成了，那么我们就换一个数字进行判断，让right–去下一个区间进行判断的操作了

但是现在如果a+b<c的话，因为a和b中间的数都小于等于b

如果right--的话，结果只会更小了，这种就没有结果了，所以直接更换a的值

a加上小于等于b的这堆数只会更小了，没有可能大于c的，所以我们直接将2划掉

所以我们进行left++，去下一个区间进行操作

上面说的情况我们的10是一个固定值，所以我们当10的三角形找到完成之后我们会一个固定值进行计算三角形个数

对于这个题我们的思路如下 ： 1.我们先固定最大的数（在数组的最后一个，因为这个数组可以进行排序的操作）

2.在最大的数的左区间内，使用双指针算法，快速统计处符合要求的三元组的个数

固定最大的数我们固定n次,时间复杂度是o(n)

双指针相向移动，时间复杂度是o(n)

所以我们的时间复杂度是o(n^2)

3.代码部分

class Solution {
public:
   int triangleNumber(vector<int>& nums)
   {
       //1.优化--排序操作
       sort(nums.begin(),nums.end());//这个就是对数组进行一个排序操作
       
       //2.利用双指针来进行问题的解决
       int ret=0;
       int n=nums.size();//计算数组个数
       for(int i=n-1;i>=2;i--)//先固定最大的数，因为上面我们已经排序过了，所以我们直接从最后一个数开始
       //我们这里的i>=2,为什么呢？因为我们固定的是一个三元组，如果一个数组存在三个数字的话，并且是排好序的，那么这个最大的数字的下标就是2
       {
           //利用双指针快速统计符合要求的三元组的个数
           int left=0,right=i-1;//就是固定的位置左边的那个数
           while(left<right)//左指针小于右指针
           {
               if(nums[left]+nums[right]>nums[i]) //两个指针指向的数大于固定的数，我们就进行次数的计算
               {
                   ret+=right-left;//a和b区间中比a大的数都能和b进行一个匹配然后和固定数进行一个比较的操作，次数总共是right-left次，这样直接更加快速
                   right--;//然后让right进行--操作，
               //这里我们第一步就是统计个数，第二步就是移动指针
               }
               else//这个就是a+b<c的情况，因为排好序了，所以我们将最小的a 换一个新的数字，就是a++
               {
                   left++;
               }
           }
       }
       return ret;
   }
};
//for(int i=n-1;i>=2;i--)
//我们在循环中每次过后,i--就会切换这个固定的值

3.代码分析

我们先对这个混乱的数组进行一个排序的操作，我们直接使用sort进行排序的操作 然后我们就可以利用双指针进行问题的解决操作 我们先计算数组元素个数

我们先使用这个外层for循环进行这个排序好的数组的最后一位的固定，这个数通常是最大的 我们将这个最大的数进行一个固定的操作 我们利用for循环，我们设置i从n-1开始，就是最后一个数的下标 然后我们结束的条件是i>=2，然后每次循环结束让i-1,就是换一个固定的数

然后我们利用双指针快速统计符合条件的三元组的个数 我们创建两个指针，然后左指针指向0，右指针指向i-1就是倒数第二个数开始 然后我嫩进行一个wile循环的操作 循环的条件就是left得小于right，不能存在越界的情况 在while循环中，我们得判断，如果左指针和右指针指向的数加在一起小于固定的数，我们就可以让left往右边走，因为右边的数比较大，但是我们是不能动右指针，因为右指针当前就是最大了的 然后如果左右指针指向的数加起来大于固定的数的话， 那么我们左指针和右指针中间的数和右指针加起来都比这个固定的数大，因为中间的数都比左指针指向的数大些 然后，我们就不需要继续进行循环操作了，我们直接计算中间有多少个数，直接加在我们的返回值里面就行了 然后这里算完了我们就让right--

然后出了循环的话，我们换一个固定的数继续进行操作 那么就是for循环里面的i减减了 然后最后我们将累计的数值直接进行返回操作就行了

3. 和为S的两个数

题目传送门

3.1 题目说明

题目是关于在一个升序数组中查找两个数，使它们的和等于给定的值 S，如果有多对数字的和等于 S，返回任意一组即可。如果不存在这样的数字对，返回空数组。

• 输入:
  • 一个升序数组 array
  • 一个目标和 S
• 输出:
  • 找到两个数的和等于 S，返回这两个数的数组。如果有多个解，可以返回任意一个。
  • 如果没有解，返回空数组。

数据范围 ：

• 数组长度范围：

• 数组元素范围：

实例1

• 输入: [1, 2, 4, 7, 11, 15], 15
• 输出: [4, 11]
• 解释: 返回 [4, 11] 或者 [11, 4] 都是正确的。

实例2

• 输入: [1, 5, 11], 10
• 输出: []
• 解释: 不存在和为 10 的两个数，返回空数组。

实例3

• 输入: [1, 2, 3, 4, 5], 5
• 输出: [1, 4]
• 解释: 可以返回 [1, 4], [4, 1], [2, 3], [3, 2]。

3.2 题目分析

题目说让我们输入一个升序的数组和一个数字s，在数组中查找两个数，这两个数之和刚好等于s。然后将这两个数返回就行了 如果存在多组的话，返回一组就行了，如果没找到的话，返回一个空数组就行了 那么对这个题的话我们的哥想到的就是把这个数组所有的数都拿出来，然后使用暴力解法一个个加，将所有的情况算出来 暴力枚举直接两个for循环就可以解决了

除了暴力枚举的方法，我们可以利用单调性，使用双指针算法进行解决问题，这个效率也是比暴力枚举更高

具体说明： 我们先定义两个指针，一个left指向我们第一个数，一个right指向我们最后一个数

这里的话我们2和21相加已经比30小了，那么2就没必要和区间之间的数进行相加了，因为都比21小了，这个right是区间中最大的数了，我们让left++

现在我们的11+21=32>30

那么我们应该舍去那个数呢？

我们应该将这个right这个数去掉，因为left和right中间的数都比left大，如果将left舍去的话，那么选择区间中间的数那么结果只会更大，所以我们需要让right变小点，right--

如果我们找到符合条件的两个对应的值我们直接进行返回的操作

利用数组有序的特性，通过一次判断 我们可以舍去掉很多的数，这个时复杂度很快 时间复杂度就是o(n)

3.3 代码部分

class Solution {
public:
    vector<int> FindNumbersWithSum(vector<int> array,int sum)
    {
        int left=0,right=array.size()-1;
        while(left<right)
        {
            int tmp=array[left]+array[right];
            if(tmp>sum)//我们算的值大于给的sum值，我们就将right往左边挪一位
            {
                right--;
            }
            else if(tmp<sum)//我们算的值小于sum的话，我们直接将left进行++操作
            {
                left++;
            }
            //tmp=sum的情况，我们直接将这个符合的两个数字进行返回的操作就行了
            else return {array[left],array[right]};//将这连个变量括起来我们就能进行返回操作了
        }
        //照顾编译器我们会强行返回一个结果的
            return { };
    }
};

3.4 代码分析

我们先定义了两个指针，left和right，让left指向我们的下标为0的元素，right指向我们的下标为n-1的元素，这里的n是数组的元素大小 然后我们利用循环找到符合条件的两个数 我们先创建两个变量将这个left和right所指向的数的和进行保存了 然后我们进行比较，如果当前的和大于我们要找到的和，就让right往左边走，相反就是让left往右边走 因为这个数组是有序的，从小到大进行排序的 除了上面的两种情况，就是我们的符合条件的情况，我们直接将这两个元素进行返回的操作就行了

先定义好左右指针，然后将左右指针相加的结果与sum进行一个比较的操作

如果小于的话就将left++

如果大于的话就将right--

如果等于的话我们直接将这两个数返回就行了



记住，这个序列默认的是升序的