【算法专题】双指针算法

1. 移动零

题目分析

对于这类数组分块的问题，我们应该首先想到用双指针的思路来进行处理，因为数组可以通过下标进行访问，所以说我们不用真的定义指针，用下标即可。比如本题就要求将数组划分为零区域和非零区域，我们不妨定义两个指针cur和dest，cur不断向后遍历，dest则指向已处理区间内最后一个非零元素，当cur找到一个非零元素时，就把dest++并交换dest和cur对应的数组元素

那么在处理数组的过程中，数组被划分为了三块区域：

[0, dest]  [dest+1, cur] [cur+1, n-1]

分别代表：非零区域、零区域、未处理区域

当处理结束后只剩下非零区域和零区域了，而我们也实现了题目的要求，把数组中的所有元素都移动到数组末尾，且不改变其他元素的次序

实现代码：

class Solution {
public:void moveZeroes(vector<int>& nums) {int dest = -1, cur = 0; // 我们一开始并不知道dest的位置，暂时定义为-1while(cur < nums.size()) {if(nums[cur] == 0) {cur++;}else if(nums[cur] != 0) {dest++;swap(nums[dest], nums[cur]);cur++;}}}
};

2. 复写零

 1089. 复写零 - 力扣（LeetCode）

题目描述：

依据题意，数组中的零是会被重复写一遍的，那么一旦数组中有0，数组后面肯定就会有元素被覆盖掉，所以我们肯定是不能从前向后进行处理的。

为了保证不漏掉元素，我们应该要找到最后一个没有被覆盖的元素，然后把这个元素填到数组最后面，接着向前遍历，如果碰到的元素是非零，就填一次，如果是零就填两次，这样就实现了把所有的零都复写一遍，显然这个过程我们还是需要两个指针来帮助我们完成覆盖的操作。

所以我们接下来要实现的就是：

1. 找到最后一个“复写”的数

两个指针cur和dest，cur向后遍历，当碰到0时，dest向后移动两位，否则向后移动一位，这样，当dest指向数组末尾时，cur指向的位置就是数组中最后一个需要复写的元素位置了

2. 从前向后进行复写

在第一步处理之后，dest指向了数组末尾，cur指向了最后一个要复写的下标，cur和dest开始从后往前移动，并把cur元素覆盖到dest位置上，如果cur元素为0，就覆盖两次

3. 边界情况

一般情况下，上述的第一步处理中，dest是能正常移动到n-1位置的，但是存在这样一种情况：

当数组内容如上所示时，第一步的操作就会出现问题，dest指向了数组长度之外的位置，我们需要对这种情况进行特殊处理

实现代码：

class Solution {
public:void duplicateZeros(vector<int>& arr) {int cur = 0, dest = -1;int n = arr.size();while(cur <= n - 1) // 找到最后一个复写元素{if(arr[cur]) dest++;else dest += 2;if(dest >= n - 1){break;}cur++;}if(dest == n) // 对特殊情况进行处理{arr[n - 1] = 0;cur--;dest -= 2;}while(cur >= 0) // 从后往前进行复写{if(arr[cur]) arr[dest--] =arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

3. 快乐数

202. 快乐数 - 力扣（LeetCode）

题目分析

        依题意，对于一个正整数，如果每次将其替换为每个位置上数字的平方和，那么这个数最终可能为1或进入无限循环。事实上，这一点我们是可以证明的，首先给大家讲一下鸽巢原理：如果有n个巢穴，n+1只鸽子，那么至少有一个巢穴是有两只鸽子的。然后接下来解决本题，n的范围如上，如果将其最大值替换为每个位置上数字的平方和，2^31-1 的值为2,147,483,647，就算把这十位数换成9,999,999,999，按照这个算法，结果也只有810。

        也就是说，本题n取值范围内的所有数，经过处理得到的结果都不超过810，所以只要n经过811次变换，最后一定至少出现一次重复的元素，也就进入了循环。原因是：前810次n已经将所有变换的可能结果枚举了一遍，第811次的结果必定在前810次变换结果的集合之中，所以必定重复。

算法原理

        经过上述证明，我们清楚了n经过足够多次数的变换，只可能进入重复循环或变为1，而1的平方和恒为1，也算一个循环。所以我们要判断一个数是不是快乐数，只需要判断在循环中，这个数是不是1即可。

        这就要用到快慢指针算法了，fast指针一次移动两个单位，slow指针一次移动一个单位，则一旦fast和slow相遇，就说明已经在循环中了，此时仅需判断相遇时值是否为1即可。

代码如下:

class Solution {
public:// 进行变换int getsum(int n) {int sum = 0;while(n) {int tmp = n % 10;sum += tmp * tmp;n /= 10;}return sum;}bool isHappy(int n) {int fast = n, slow = n;do {// fast每次移动两个单位，slow移动一个单位fast = getsum(getsum(fast));slow = getsum(slow);} while(fast != slow);// 最后仅需判断相遇时值是否为1return fast == 1;}
};

4. 盛水最多的容器 

​​​​​​11. 盛最多水的容器 - 力扣（LeetCode）

题目解析

        根据题目示例，我们发现容器高度是由两端的柱子中较短的一根所决定的，设其高度为h，两根柱子的距离设为l，则我们要找的就是h*l最大的组合

算法原理

解法一 暴力解法

        从起始位置开始，将所有的位置都枚举一遍，最后肯定能找到盛水最多的容器，时间复杂度是O(n^2)但这样做肯定是会超时的，我们必须想一种更优秀的方法

解法二 双指针算法

        我们先用一个小区间来举例子，在题目解析中，我们看出了，容器高度由两端中较短的一方决定。在这个例子中，如果我们固定较短的柱子，移动另一端，可以发现，容器的容积是在减小的，问题在于：

1. 向内枚举，区间长度是一定减小的

2. 固定了短端，移动另一端，如果另一端比短端短，高度减小；就算比短端长，高度也不会变大

        所以趋势是：l一定减小，h不变或减小，v = h * l，则容积也必定减小！

        而如果我们固定较长的柱子，移动另一端，情况则有不同，如果短端找到更长的柱子，容器的容积是有可能增大的

        所以我们可以定义两个指针left、right在区间的0和n-1位置，找到短的一方，计算出当前容积，移动长的一方，这样我们只需要遍历数组一遍就能够找到最大值，时间复杂度为O(n)

class Solution {
public:int maxArea(vector<int>& height) {int l = 0, r = height.size() - 1;int h, w;int v = 0;while(l != r) {h = height[l] < height[r] ? height[l] : height[r];w = r - l;int tmp = h * w;v = tmp > v ? tmp : v;if(height[l] < height[r]) l++;else r--;}return v;}
};

5. 有效三角形的个数

 611. 有效三角形的个数 - 力扣（LeetCode）

题意分析：

        我们都知道，三角形的三条边满足任意两条边之和大于第三条边，但是还有一个更进一步的结论：假设a < b < c，则只要三个数满足a + b > c，就能保证任意两边之和大于第三条边。

        因此本题就转化为了，找到数组中满足 a < b < c 且 a + b > c 的三元组个数。

算法原理：

解法一：暴力解法

        用三层for循环列举出所有的三元组，然后判断是否满足构成三角形的条件，则时间复杂度：3*n^3，进行一下优化，如果我们先把数组排序，那么判断是否满足条件就只需要一次，时间复杂度为：n*logn + n^3，显然时间复杂度还是O(n^3)，肯定是会超时的，我们需要想办法减小时间复杂度。

解法二：双指针算法

        在前面我们分析过了，要找的是满足 a < b < c 且 a + b > c 的三元组个数，和解法一中的优化一样，我们先将数组进行排序，则c肯定就在数组的末端找了，所以我们不妨先固定c，再找符合条件的a、b即可。

        可是如果我们还是用遍历的方式去找a和b，那时间复杂度根本就没有降低，还是O(n^3)，所以必须换一个思路，既然 a < b ，我们不妨定义两个指针：left，right，分别从数组左右端移动，与上一道题类似的，我们要通过单调性来决定是移动left还是right！

        如果 a + b > c，因为数组排过序，是单调递增的，left++过程中是始终满足 a + b > c 的，由于本题求的是三元组个数，没必要进行left++了，直接right - left求个数即可。之后我们再进行right--，当left  == right时，说明这个c为最长边的情况列举完了，接着求下一个c为最长边的情况。

        如果 a + b <= c，因为数组排过序，是单调递增的，如果我们让right--，a + b 只能更小，因此只能让left++，直到 a + b > c 或 left == right。

代码如下：

class Solution {
public:int triangleNumber(vector<int>& nums) {int a, b, c;int max = nums.size() - 1;int cnt = 0;sort(nums.begin(), nums.end());while(max > 1){int left = 0, right = max - 1;while(left != right){a = nums[left], b = nums[right], c = nums[max];if(a + b > c){cnt += right - left;right--;}else left++;}max--;}return cnt;}
};