【基础算法总结】双指针

一，双指针算法介绍

双指针算法是基础算法之一，一般用于涉及数组分块/数组划分这类问题 。这里的"指针"是利用数组下标或是一个数来充当的。

在遍历过程中，两个指针的位置：
cur：从左往右扫描数组，遍历数组。
dest：指向已处理的区间内，非0元素的最后一个位置。如下图

所以两个指针把数组分成了三个区间：

二，算法原理和代码实现

283.移动零

算法原理：

我们也是定义两个变量 cur 和 dest，根据上面介绍的两个指针的位置，初始化 cur = 0, dest = -1。

在 cur 从前往后遍历的过程中，无非两种情况：
1. 遇到0元素：cur++
2. 遇到非0元素：先swap(dest+1, cur), 再cur++, dest++

代码实现：

class Solution 
{
public:void moveZeroes(vector<int>& nums) {for(int cur = 0, dest = -1; cur < nums.size(); ){if(nums[cur] == 0) cur++;else swap(nums[dest+1], nums[cur]), cur++, dest++;}}
};

1089.复写零

算法原理：

这道题看起来简单，但是有很多坑，很多细节。我们使用双指针先在草稿纸上模拟，不难发现从前往后复写是不行的，会覆盖后面的数据。但是要如何从后往前复写呢，起始位置怎么确定？

所以解决这个题有两个步骤：

1. 先找到最后一个复写的数。
这一步骤也要用双指针算法：

当走完这个双指针，此时 cur 指向的数就是最后一个要复写的数，dest 指向的位置就是开始复写的第一个位置。
2. 再从后往前进行复写操作：
在 cur 从后往前遍历的过程中，无非两种情况：
(1) 遇到0元素：dest向前复写两个0,cur–,dest -= 2
(2) 遇到非0元素：先arr[dest] = arr[cur], 再cur++, dest++

细节/技巧问题：

(1) 在第一步的第三小步中，一定要先判断 dest 是否已经结束
(2) 还要处理一种特殊情况：[1,0,2,3,0,4]。根据第一步的双指针，此时dest会越界，就要做特殊处理，当 dest == n 时，直接把 arr[n-1] = 0, cur–, dest -= 2。

代码实现：

class Solution
{
public:void duplicateZeros(vector<int>& arr){// 找到最后一个要复写的位置int cur = 0, dest = -1, n = arr.size();while (cur < n){if (arr[cur]) dest++;else dest += 2;if (dest >= n - 1) break;cur++; // 注意每次++之前都要先判断dest是否越界}// 处理特殊情况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 - 1] = 0;dest -= 2;cur--;}}}
};

下面是一开始我写的错误代码，以示警戒：

class Solution
{
public:void duplicateZeros(vector<int>& arr){// 先找到最后一个要复写的数int n = arr.size();int cur = 0, dest = -1;for (; dest < n - 1;){if (arr[cur] != 0) dest++;else dest += 2;if (dest != n - 1)cur++;}// 处理边界情况if (dest == n) arr[n - 1] = 0, cur--, dest -= 2;// 从后往前完成复写操作for (; cur >= 0 && dest >= 0; ){if (arr[cur] != 0) arr[dest] = arr[cur], dest--;else arr[dest] = 0, arr[dest - 1] = 0, dest -= 2;cur--;}}
};

202.快乐数

算法原理：

首先来理解题目：

所以这道题可以抽象成另类的 “链表是否带环问题”。只不过这道题是一定带环的，只要根据环内的数进行判断即可。

使用经典的快慢双指针算法：
(1) 定义快慢指针
(2) 慢指针每次向后走一步，快指针向后走两步
(3) 判断相遇时候的值即可

拓展：为什么这个题一定成环？

使用鸽巢原理证明。

细节/技巧问题：

(1) 这题的双指针不再是数组下标，而是一个数。
(2) 在进入第一次循环时，先让 fast 指向第二个数，不然进不了循环。

代码实现：

class Solution 
{
public:bool isHappy(int n) {int slow = n, fast = mypow(n);while(slow != fast){slow = mypow(slow);fast = mypow(mypow(fast));}if(slow == 1)return true;elsereturn false;}int mypow(int n){int sum = 0;while(n){int a = n % 10;n /= 10;sum += a*a;}return sum;}
};

11.盛最多水的容器

算法原理：

解法1：暴力枚举，O(N*N)。这应该是大家心中第一个闪过的想法，就是使用两层for循环计算出全部体积，再求出最大值。但是这个解法超时。

解法2：利用单调性，使用双指针，O(N)
首先观察一个规律：
我们固定一个数，再向外枚举，会出现下面的情况，结果都是缩小，就可以把这个数直接抹去，避免无用枚举。

所以可以把这个规律推广到全部数据：

定义两个指针指向开头和结尾，此时可以计算出一个体积，根据上面的规律把较小的那个高度直接舍去，指针向里缩，继续计算体积…，直到两个指针相遇，统计出最大体积。

细节/技巧问题：

体积= 高度 * 宽度。根据木桶原理，高度是小的那个，而宽度是两个下标相减。

代码实现：

class Solution 
{
public:int maxArea(vector<int>& height) {int cur1 = 0, cur2 = height.size() -1;int maxV = 0;while(cur1 <= cur2){int H = min(height[cur1], height[cur2]);maxV = max(maxV, (cur2 - cur1) * H);// 利用单调性if(height[cur1] < height[cur2]) cur1++;else cur2--;}return maxV;}
};

611.有效三角形的个数

算法原理：

首先补充一个数学知识，只要一次判断，得出是否能构成三角形：

若a <= b <= c 且 a +b > c，则可以构成三角形。
所以可以得出一个优化：先把数组排序，O(N*logN)。

数组排完序后：

解法1：暴力枚举，O(N*logN + N^3)，三层for循环，绝对超时。

解法2：利用单调性，使用双指针算法,O(N*logN + N^2)。
(1) 先用c固定最大的元素，定义left 和right分别指向第一个元素，c的下一个元素。
(2) 若nums[left] + nums[right] > nums[c]，由于left和 right之间的数都比 nums[left] 大，与 nums[right] 相加后一定大于c，构成三角形了，就不要一个个枚举了，直接right- -。
(3) 此时三角形个数 = right - left。
(4) 若nums[left] + nums[right] <= nums[c]，由于left和 right之间的数都比 nums[right] 小，与 nums[left] 相加后一定小于c，也不要一个个枚举了，直接left++。
(5) 以上是走完一趟的个数，再c–，固定下一个数。

代码实现：

class Solution 
{
public:int triangleNumber(vector<int>& nums) {// 排序sort(nums.begin(), nums.end());int n = nums.size();int ret = 0; // 记录个数for(int c = n-1; c >= 2; c--){int left = 0, right = c - 1;while(left < right){if(nums[left] + nums[right] > nums[c]){ret += right - left;right--;} else left++;}}return ret;}
};

LRC179.和为s的两个数

算法原理：

解法1：暴力枚举，两层for循环，O(N^2)，绝对超时。没有好好利用单调递增这个特性!!

解法2：和上一题的解法2类似，也是利用单调性和双指针算法，O(N)。

细节/技巧问题：

找到数对后就直接 break 结束循环。

代码实现：

class Solution 
{
public:vector<int> twoSum(vector<int>& price, int target) {vector<int> ret;int left = 0, right = price.size() - 1;while(left < right){int sum = price[left] + price[right];if(sum > target) right--;else if(sum < target) left++;else {ret.push_back(price[left]); ret.push_back(price[right]);break;}}return ret;}
};

15.三数之和

算法原理：

解法1：排序+暴力枚举+利用set去重，O(N^3).

解法2：排序+双指针，O(N^2).
这道题其实是上一题的进阶版，首先排序，再固定一个数 a，在该数后面的区间内使用双指针算法快速的找到两个数的和是 -a。

难点/细节/技巧：

这道题的算法不难想，难的是保证不重不漏。

(1) 去重操作有两个方面：一是找到一种结果后，left 和 right 指针要跳过重复元素，二是当使用完一次双指针后，i 也需要跳过重复元素，此时要注意越界。
(2) 还有一个小优化就是当固定的那个数是正数时，后面再也找不到两数和为负数了，直接结束。

代码实现：

class Solution 
{
public:vector<vector<int>> threeSum(vector<int>& nums){// 排序sort(nums.begin(), nums.end());vector<vector<int>> vv;int n = nums.size();for(int i = 0; i <= n-3; i++) // 固定数 a{if(nums[i] > 0) break; // 小优化int left = i +1, right = n-1, a = nums[i];// 双指针while(left < right){int sum = nums[left] + nums[right];if(sum > -a) right--;else if(sum < -a) left++;else {vv.push_back({nums[i], nums[left], nums[right]});// 去重，注意越界while(left < right && nums[left] == nums[left+1]) left++;while(left < right && nums[right] == nums[right-1]) right--;left++;right--;}}while(i < n-1 && nums[i] == nums[i+1]) i++;}return vv;}
};

18.四数之和

算法原理：

本道题又是上一题的进阶版。

难点/细节/技巧：

这道题会出现数据溢出的风险。所以当计算两个固定是数之和时，类型定义为 long long。
其余细节参考上一题。

代码实现：

class Solution 
{
public:vector<vector<int>> fourSum(vector<int>& nums, int target) {// 排序sort(nums.begin(), nums.end());int n = nums.size();vector<vector<int>> vv;for(int i = 0; i < n; i++) // 固定数a{// 三数和for(int j = i+1; j < n; j++)// 固定数b{// 双指针算法int left = j+1, right = n-1;long long t = (long long)target - (nums[i] + nums[j]);while(left < right){long long sum = nums[left] + nums[right];if(sum > t) right--;else if(sum < t) left++;else{vv.push_back({nums[i], nums[j], nums[left], nums[right]});// 去重while(left < right && nums[left] == nums[left+1]) left++;while(left < right && nums[right] == nums[right-1]) right--;left++;right--;}}while(j < n-1 && nums[j] == nums[j+1]) j++;}while(i < n-1 && nums[i] == nums[i+1]) i++;}return vv;}
};

三，算法总结

双指针算法是一种基础，但是十分经典的算法。通过上面的若干道题可知，"双指针"使用起来是十分灵活的，有时代指数组下标，有时也可以代指一个数。使用双指针算法的关键之一就是要控制好边界，稍不留神就会出现数组越界的问题，并且在使用这个算法时强烈建议各位一定要多画图，光靠想象容易出错并且会忽略很多细节问题。