双指针算法的妙用：提高代码效率的秘密（2）

双指针算法的妙用：提高代码效率的秘密（2）

前言：

小编在前几日讲述了有关双指针算法两道题目的讲解，今天小编继续进行有关双指针算法习题的讲解，老规矩，今天还是两道题目的讲解，希望各位在看完我这篇文章后有所收获，那么废话不多说，下面我们进入算法时间！

1.快乐数

1.1.题目展示

老规矩，先来各位大家展示题目来源：202. 快乐数 - 力扣（LeetCode）

1.2.题目解答

我们先来观赏一下这个题目，这个题目读起来是很短的，它是想要我们去判断一个快乐数，并且给出了快乐数的定义，小编简单的概述一下：

1. 定义一个正整数，每次让它等于它每个位（个，十，百等等）的数的平方和。
2. 重复的进行上述平方和的操作，最后会出现两个结果：（1）.无限循环直到变成1；（2）.无限循环但是永远不到1.
3. 如果最后一直循环的是1的话，我们就证明出这个数就是快乐数~

下面我们进入本题的思路讲解部分。

1.3.题目思路讲解

这个题目一拿到手可能会让部分读者朋友犯愁，其实这题就是纸老虎——看着吓人，其实不难，我们只要把思路捋顺就好，此时我们先看一个快乐数是如何得到的：

上面就是一个快乐数的得法，如果我们仅仅看这个例子，是总结不出来快乐数得到的方法，这个题目给出的第二个例子，就恰好让我们知道了快乐数一个隐藏的性质：

此时我们不难看出，如果这个数不是快乐数的话，会形成一个死循环，而不是单纯的无限循环，这是题目没有告诉我们的，如果题目告诉了我们这个性质，那么这个题目就是信手拈来，但可惜的是，当我们第一次见到这个题目，可能就会因为这个没告诉我们的隐藏性质而直接傻眼，这就告诉我们要巧用题目给出的例子，上面两个就是题目给出的例子，我们通过例子就可以推出这个隐藏性质，下面我就依靠这个性质来给各位讲述一下这个题目是如何解决的。

首先，各位要知道，其实快乐数也是形成了一个循环，只不过这个循环是以1进行的循环，非快乐数是会从开头就进入一个死循环的，最后还是会回到开头，可能听到这里，曾经看过我链表习题的读者朋友就想到了一个和这个题目类似的题：判断循环链表的题目，下面我放上那个博客的链接：单链表习题——快慢指针类习题详解！（2）-CSDN博客，这个题目和那个题目用到的是同一个思想，都需要采用快慢指针实现，我们都晓得快慢指针在一个循环的链中，总是可以相遇，如果相遇了就说明这个链子是循环的，此时我们就是要使用快慢指针来判断快乐数，如果快慢指针相遇的时候，此时的二者都是1的话，那么这个数就是快乐书；反之则不是快乐数，这便是这个题目的解题方法，下面小编展示这个题目的代码书写。

1.4.代码讲解

我们首先需要一个函数，它的作用就是来进行让一个数的每个位进行平方然后求和，在返回这个数，这是得到快乐数的其中一步，由于代码的难度不大，小编就不讲解了（如果有看不明白的读者朋友可以私信小编，小编会进行更详细的解答）：

int getshort(int n)
    {
        int sum = 0;
       while(n)
       {
         int x = n % 10;
         sum+= x * x;
         n = n / 10;
       } 
       return sum;
    }

之后我们进入主函数的书写，此时我们就和之前循环链表一样，先设置好快慢指针，刚开始让他们都是给定的n，之后我们就进入循环了，此时循环的条件是不太重要的，我就用1来代替了（因为之后我们肯定会判断出是否是快乐数，判断完后直接返回true或者false，循环会自动结束的），循环体内部，我们先让慢指针进行一次平方和，快指针进行两次平方和；之后我们判断二者是否相等，如果相等并且均等于1的话，那么我们返回true，证明此时为快乐数；如果相等但不等于1的话，那么就返回false，证明此时不为快乐数；如果不相等的话，继续循环，直到二者相等为止，此时我们就完成了主函数的书写下面小编给出这部分的代码：

    bool isHappy(int n) {
         //先设置好快慢指针
         int _short = n,_long  = n;
         while(1)
         {
            _short = getshort(_short);
            _long = getshort(_long);
            _long = getshort(_long);
            if(_short == _long && _short== 1)
            {
                return true;
            }
            else if(_short == _long && _short!= 1)
            return false;
         }
    }

以上便就是这个代码的所有，下面我给出完整代码并进入下个题目的讲述。

class Solution {
public:
    int getshort(int n)
    {
        int sum = 0;
       while(n)
       {
         int x = n % 10;
         sum+= x * x;
         n = n / 10;
       } 
       return sum;
    }
    bool isHappy(int n) {
         //先设置好快慢指针
         int _short = n,_long  = n;
         while(1)
         {
            _short = getshort(_short);
            _long = getshort(_long);
            _long = getshort(_long);
            if(_short == _long && _short== 1)
            {
                return true;
            }
            else if(_short == _long && _short!= 1)
            return false;
         }
    }
};

2.盛最多水的容器

2.1.题目展示

老规矩，小编给出本题目的来源：11. 盛最多水的容器 - 力扣（LeetCode）

2.2.题目讲解

首先，我先给各位打个强心剂，不要看这个题目难度是困难的各位就退缩了，其实这个题目的难度还是不算大，只要我们认真看完题目，并且懂了大概意思，这个题目就直接难度下降了，下面通过例题的图片来进行讲述：

通过题目的描述，我们容易知道这个题目是想让我们去求一块区间的最大体积，就拿上图所示，此时当高度为8和高度为7之间的区间体积应该是最大的，此时V=7 * （右 - 左）就可以求出来体积，这个题目就是想让我们去求一下任意两个区间的体积，求出其中的最大值，题目理解其实就是这么的容易，下面小编讲述一下这个题目的完成思路。

1.3.题目思路讲解

1.3.1.暴力解法

其实本题目一般读者拿到手的时候，第一个想到的往往就是采用暴力解法来进行做，此时题目会给我们一个数组的区间，此时我们仅需从第一个数开始进行一层循环，让它和它下一个的元素进行体积求解，直到把所有的体积求出来为止，虽然这么做是这个题目最简单的算法，但是，它的时间复杂度是非常大的，因为是套用两次循环，所以我们不难算出时间复杂度应该是：O（N^2），小编尝试过，这么做是无法在规定时间内完成这个题目的，所以这个暴力求解算法直接out掉，不过我们可以在暴力解法的基础上，进行算法的升级，下面小编讲述一个升级后的算法——双指针算法。

1.3.2.双指针算法

在讲述双指针算法之前，小编先简单的讲述一个小小的数学上的小技巧（关于单调性的），此时我们就拿例1的子数组来进行这个思路的讲解：

此时我们先计算这个小区间水的体积，我们就已2为左，8为右，不难发现此时的体积应该是2 * 3 = 6，此时我们在缩小区间，如果让右边的8往内走的话，此时的高度不变，长度变小，所以对应着的体积就会变小，所以说这么继续往后走是没有任何意义的，如果此时我们让2往里面走的话，此时的长度小了，高度大了，体积经过计算发现也大了，所以说，我们不拿看出一个小小的规律，如果此时我们先通过整个区间进行体积的计算，算出一个值后进行存储，然后比较左右两端的值，谁小谁就往里面走，直到左右相遇的时候便把一个数组便利完了，这其实就是这个题目的大致解法，可能我这么简单一说各位也不懂，下面我就通过图文的方式来介绍如何通过双指针进行这个题目的解法。

首先，我们准备一个数组，我就用例1的数组进行讲解，先定义好两个指针（cur和dest），一个指向左（cur），一个指向右（dest）：

之后我们先记性两个位置的容器大小的计算，此时我们不难看出，高度是1，长度是：8，所以求得8；之后我们在进行两个头元素大小的比较，让小的继续里面走：

之后通过一个while循环，我们便可以得出一个相对区间的最大面积，最后我们把得出来的这些面积存储到一个vector容器里面，然后我们把元素拿出来进行比较，去到最大值，此就是盛水的最大量，以上就是思路讲述部分，下面进入代码实操部分。

1.4.代码讲解

首先，通过上述我讲述的思路不难看出，我们需要先右一个函数，这个函数是来进行比较两个数求出高，此时这个代码其实很容易去书写，我就不仔细解释了（如果不懂的私信问我，我会及时回复）：

    int getmin(int a,int b)
    {
        if(a < b)
        return a;
        else
        return b;
    }

之后，我们还需要一个函数，小编在最后一步说了，我们需要遍历完所有求出的体积，找到其中体积最大的，这个其实也好实现，找最大值函数想必各位之前在学习C语言的时候就写过（不仅仅局限于C语言，只要学校讲述了编程语言，这个算是一个很基础很基础的函数了），下面小编给出这个函数的书写：

int getmax(vector<int>& arr)
    {
        int max = 0;
        for(int i = 0 ; i < arr.size() ; i++)
        {
            if(arr[i] > max)
            max = arr[i];
        }
        return max;
    }

预备工作做完以后，下面我们就进入主函数的讲述部分，此时我们先设置好两个指针以及新开出一个容器用来存放体积，一个指针指向开始，一个指针指向最后，此时我们开始进行体积的求解，我们就要用到一个循环来进行求解，循环的条件自然是左要小于右，然后在循环体内，我们开始求出最小高度，之后把高度乘以两数之间的距离的值放入到容器内，然后比较左右，如果左大于右，那么让右往里面走，若左小于右，让左往里面走，此时不断循环，我们就可以求出每个区间的最大容量，之后我们直接返回所有容量的最大值，通过调用上面的返回最大值函数来进行最大值的返回，这么做的话主函数就可以写完了：

    int maxArea(vector<int>& height) 
    {
        size_t _left = 0,_right = height.size() - 1;
        vector<int> arr;
        while(_left < _right)
        {
           int h = getmin(height[_left],height[_right]);
           arr.push_back(h * (_right - _left));
           if(height[_left] > height[_right])
           _right--;
           else _left++;
        }
        return getmax(arr);
    }

以上便就是代码部分的讲解，下面小编给出完整的代码：

class Solution {
public:
    int getmax(vector<int>& arr)
    {
        int max = 0;
        for(int i = 0 ; i < arr.size() ; i++)
        {
            if(arr[i] > max)
            max = arr[i];
        }
        return max;
    }
    int getmin(int a,int b)
    {
        if(a < b)
        return a;
        else
        return b;
    }
    int maxArea(vector<int>& height) 
    {
        size_t _left = 0,_right = height.size() - 1;
        vector<int> arr;
        while(_left < _right)
        {
           int h = getmin(height[_left],height[_right]);
           arr.push_back(h * (_right - _left));
           if(height[_left] > height[_right])
           _right--;
           else _left++;
        }
        return getmax(arr);
    }
};

3.总结

此时今天的两道题目到这里也就结束了，小编认为自己写的还是有些不太好，因为在写第二个题目的时候我忘记了相关的算法了，直到我重新看了一遍曾经的笔记后才想起来这个题目的解法，这个故事告诉我们要温故而知新，所以说第二个题目的讲解相对比较差一点，如果有错误，可以在评论区“批评”我，我还是很乐意接受各位的建议的，讲题的时光永远很短暂，那么各位大佬们，我们下一篇文章见啦！