【优选算法】探索双指针之美（一）:双指针与单调性的完美邂逅

前言：

在上一章中我们已经认识到了双指针，在这章里我们就来探索一下当双指针和单调性遇见后会擦出怎样的火花呢？

我们就先来几道例题探索一下吧!

1.盛水最多的容器

题目链接： 11.盛水最多的容器
题目叙述： 给定一个长度为 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。

解题思路：
  解法一：暴力枚举
固定最左端和右边的数依次匹配。
伪代码：

for(i = 0; i < n;i++)
   for(j= i + 1;Ij < n; j++)

时间复杂度：O(n^2)

  解法二：利用单调性，使用双指针解决
 1. 首先定义一个left指针和一个right指针分别指向数组的最左端和最右端。
 2. 容器的体积：v = 长 * 高
  长： right - left 高：left和right两者分别对应的最小的一个
  根据木桶原理：
  容器的储水量v = (right - left) * min(nums[left],nums[right])
  （其中min(nums[left],nums[right])表示的是left和right两者分别对应的最小的一个.）
  举个例子：[6 , 2 ,8 , 4]
  让left指向6这个位置right指向4这个位置
  v = 3 * 4 = 12，v = 长 * 高，其中高不变，长减小，容器的  体积减小，所以right指向4不动，left无论指向2还是5，容器的体积总是减小，原因是高不变，长减小了（小的数向内枚举结果变小）所以只需让right--再次判断，现在right指向8这个位置，v = 2 * 6 = 12，right指向8左边的任何一个数容积都会减小，此时left++,以此类推。

 代码实现

class Solution {
public:
    int maxArea(vector<int>& height) {
        int left = 0,right = height.size() - 1; int ret = 0;
        while(left < right)
        {
            int v = min(height[left],height[right]) * (right - left);
            ret = max(v,ret);
            //更新指针
            if(height[left] < height[right]) left++;
            else right--;
        }
        return ret;
    }
};

时间复杂度：O(n)

2.有效三角形个数

题目链接：611.有效三角形的个数
题目叙述： 给定一个包含非负整数的数组 nums，返回其中可以组成三角形三条边的三元组个数。

示例 1:

输入: nums= [2,2,3,4]
输出: 3
解释: 有效的组合是:
2,3,4 (使用第一个 2)
2,3,4 (使用第二个 2)
2,2,3
示例 2:

输入: nums =[4,2,3,4]
输出: 4

解题思路：
给定三个数判断能否构成三角形， 只需判断三个数中最小的两个数的和是否大于最大的数
优化：先对整个数组排序

  解法一：暴力枚举
伪代码：

for(i = 0;i < n;i++)
   for(j = i + 1;j < n;j++)
      for(k = j + 1;k < n;k++)
          check(i,j,k);

时间复杂度：O(n^3)

  解法二：利用单调性，使用双指针算法来解决
 利用a + b > c
 举例数组[2,2,3,4,5,9,10]
 1. 先对整个数组进行排序
 2. 定义一个变量c固定最大的数10，定义left指向第一个元素2(a)，right指向c的前一个位置9(b)。a + b = 11 > c,我们会发现a以及a右边到5的数加起来总比c大，因为这个数组是有序的a + x > c,那么a加上比x大的任何数总比c大。这时共有right - left种情况.这时只需--right.
如果a + b <= c只需++left.

 所以共会出现三种情况a + b > c,a + b < c和a + b = c后两者可以归为一种情况:
   ○a + b > c ,--right
   ○a + b <= c ,++left
 2.固定下一个最大的数9，依次

代码实现：

class Solution {
public:
    int triangleNumber(vector<int>& nums) {
        //1. 优化
        sort(nums.begin(),nums.end());

        //2. 利用双指针解决问题
        int ret = 0 , n = nums.size();
        for(int i = n - 1;i >= 2;i--) //先固定最大的数
        {
            int left = 0,right = i - 1;
            while(left < right)
            {
                if(nums[left] + nums[right] > nums[i])
                {
                    ret += right - left;
                    right--;
                }
                else
                left++;
            }

        }
        return ret;
    }
};

时间复杂度：O(n^2)

3. 和为s的两个数字

题目链接：和为s的两个数字
题目描述： 输入一个递增排序的数组和一个数字 s，在数组中查找两个数，使得它们的和正好是 s。如果有多对数字的和等于s，则输出任意一对即可。

示例 1：
输入： nums = [2, 7, 11, 15], target = 9
输出： [2, 7]或者 [7, 2]

解题思路：
 解法一：暴力枚举
伪代码：

for(i = 0;i < n;i++)
   for(j = i + 1;j < n;j++)
       check(nums[i] + nums[j] == target);

时间复杂度：O(n^2)

 解法二：利用单调性，使用双指针解决问题
 定义两个指针，left指向第一个元素，right指向最后一个元素；定义一个sum为left和right指向的元素之和。
  •sum > target  right--
  •sum < target  left++
  •sum = target  返回结果
代码实现：

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        int left = 0, right = nums.size() - 1;
        while (left < right) {
            int sum = nums[left] + nums[right];
            if (sum > target) right--;
            else if (sum < target) left++;
            else return {nums[left], nums[right]};
        }
        //这是为了照顾编译器，不然编译器报错：不是所有的路径都有返回值
        return {-1, -1};
    }
};

时间复杂度：O(n)

4. 三数之和

题目链接：LCR 007. 三数之和
题目描述： 给定一个包含 n个整数的数组nums，判断nums中是否存在三个元素 a ，b，c ，使得 a + b + c = 0 ？请找出所有和为 0 且不重复的三元组。

示例 1：

输入：nums= [-1,0,1,2,-1,-4]
输出：[[-1,-1,2],[-1,0,1]]
示例 2:

输入： nums = []
输出：[]
示例 3：

输入： nums = [0]
输出：[]

解题思路：
 解法一：排序+暴力枚举+利用set去重
 先对数组进行排序，然后从左向后依次枚举

时间复杂度：O(n^3)

 解法二：排序+双指针
 ① 排序
 ②固定一个数a
 ③在该数后面的区间内，利用“双指针算法”快速找到两个的和为-a的即可

 处理细节问题：
1.去重
 ① 找到一种结果后，left和right指针要跳过重复元素
 ②当使用完一次双指针算法后，i也需要跳过重复元素
  避免越界
2.不漏
 找到一种结果后，不要“停”，缩小区间，继续寻找
代码实现：

class Solution {
public:
    vector<vector<int>> threeSum(vector<int>& nums) {
        vector<vector<int>> 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;
    }
};

时间复杂度：O(n^2)

5. 四数之和

题目链接：18. 四数之和
题目描述： 给你一个由 n个整数组成的数组nums ，和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组[nums[a], nums[b], nums[c], nums[d]]（若两个四元组元素一一对应，则认为两个四元组重复）：

0 <= a, b, c, d < n
a、b、c和 d互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。

示例 1：

输入： nums = [1,0,-1,0,-2,2], target = 0
输出：[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2：

输入：nums= [2,2,2,2,2],target = 8
输出：[[2,2,2,2]]

解题思路：
 解法一：排序+暴力枚举+利用set去重

 解法二：排序+双指针
 ①依次固定一个数a
 ②在a后面的区间内，利用“三数之和”找到三个数，使这三个数的和为target-a即可
 三数之和：固定一个数b，在b后面的区间内，利用“双指针找到两个数，使这两个数的和为target-a-b即可”

 处理细节问题：
1.去重
使left,right,a,b不重
2.不漏

代码实现:

class Solution {
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        vector<vector<int>> ret;
        //1.排序
        sort(nums.begin(), nums.end());

        //2.利用双指针解决问题
        int n = nums.size();
        for (int i = 0; i < n - 1;) //先固定数 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) right--;
                    else if (sum < aim) left++;
                    else
                    {
                        ret.push_back({ nums[i],nums[j],nums[left],nums[right] });
                        left++;
                        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;

    }
};

时间复杂度：O(n^3)

最后想说：

通过这篇文章你是否领略到了双指针和单调性结合后对问题的绝妙优化，面对各种问题我们都能迎刃而解，真如同“山重水复疑无路，柳暗花明又一村”啊！面对各种因暴力求解而导致的超出时间限制的问题，我们利用单调性+双指针就如同如虎添翼，把题目最优化。

如果这篇文章帮助到了你，记得评论，点赞+收藏哦，如果想要了解更多关于双指针的问题，关注博主，下篇我们就来一起探索一下由双指针构成的滑动窗口 又会有怎样的“美”呢？