算法——双指针_IT分享知识网

常见的双指针算法有以下几种类型：

对撞指针： 在数组两端分别设立左右指针，通过向中间移动这两个指针来解决问题。例如，寻找数组中的两个元素，它们的和等于给定值。

快慢指针： 一个指针移动速度较快，另一个移动速度较慢。这常用于解决链表中的问题，如判断链表是否有环，找到链表的中间节点等。

滑动窗口（有专题描述：算法——滑动窗口）：使用两个指针维护一个窗口，通过移动窗口的左右边界解决问题。这类问题常见于字符串和数组处理，例如找到最短的包含所有字符的子串。

同向双指针： 两个指针方向相同，通过控制其中一个指针的位置来处理问题。例如，在一个有序数组中查找两个数，使它们的和等于给定值。

3. 应用实例

1. 移动零

题目链接：283. 移动零 – 力扣（LeetCode）

解析：看到这道题我们这样解决，即定一个左端点在第一个0处，右指针向右寻找第一个非0元素，找到后交换这两个元素，直到遍历整个数组，代码如下

class Solution { public: void moveZeroes(vector<int>& nums) { for (int left = 0, right = 0; right < nums.size(); right++) if (nums[right] != 0) swap(nums[left++], nums[right]); } };

2. 复写零

题目链接：1089. 复写零 – 力扣（LeetCode）

解析：对于这道题，我们分析一下可以发现，要想在原数组上做到复写0，我们需要从右向左复写，不然会覆盖到后面的数字，那么我们如何找到最后一个修改后数组的位置呢？那么在这里我们可以定义一个快指针dest表示慢指针所指元素是否到达数组结尾，定义一个慢指针cur表示修改后数组中末尾元素，代码如下

class Solution { public: void duplicateZeros(vector<int>& arr) { int n = arr.size(); int cur = 0; int dest = -1; while (dest < n-1) { // 若cur对应元素为0则表示需要复写，dest+=2 if (arr[cur] != 0) { dest++; } else { dest += 2; } if (dest < n-1) cur++; } // 从右向左开始复写 while (cur >= 0) { // 若dest超出数组范围，预处理末尾元素即可 if (dest > n-1) { arr[n-1] = 0; dest-=2; cur--; continue; } // 非0元素复写一次，0元素复写2次 if (arr[cur] != 0) { arr[dest] = arr[cur]; dest--; cur--; } else { arr[dest] = 0; arr[dest-1] = 0; dest -= 2; cur--; } } } };

3. 快乐数

题目链接：202. 快乐数 – 力扣（LeetCode）

解析：我们首先分析一下19是如何变为1的，即

随后我们再来分析一下2是为何变成不了1的，即

可以看到，最后整个生成快乐数的过程形成了一个环，因此我们可以使用快慢指针判断链表是否有环的思想来解决这道题（参考：OR36链表的回文结构），代码如下

class Solution { public: int transform(int n) { int ret = 0; while (n) { int num = (n % 10) * (n % 10); ret += num; n /= 10; } return ret; } bool isHappy(int n) { int slow = transform(n); int fast = transform(transform(n)); while (slow != fast) { slow = transform(slow); fast = transform(transform(fast)); } if (fast == 1) return true; else return false; } };

对于这道题来说，我们应该还有一个疑问，为什么不会到达1的时候一定会形成一个环呢？因为int类型最大值为为‭‭2 147 483 647‬‬，所以平方和最大的数是1 999 999 999，平方和为1 + 81*9 = 724。任何数的平方和都在1到724之间，724次循环之内一定有重复的，即一定会进入循环区间，从而形成环。

4. 盛多最水的容器

题目链接：11. 盛最多水的容器 – 力扣（LeetCode）

解析：分析一下题意我们可以发现，我们可以定义左右指针，分别从两端向中间遍历，哪一端低就像反方向移动一位（若左边低则left++，右边低则right–），每一次将本次计算出的面积与上一次相比较，直到遍历到最后得到最终结果，代码如下

class Solution { public: int maxArea(vector<int>& h) { int left = 0; int right = h.size()-1; int max = 0; while (left < right) { if (h[left] <= h[right]) { int tmp = h[left] * (right - left); if (tmp > max) max = tmp; left++; } else { int tmp = h[right] * (right - left); if (tmp > max) max = tmp; right--; } } return max; } };

5. 有效三角形的个数

题目链接：611. 有效三角形的个数 – 力扣（LeetCode）

解析：要想判断三个数是否能组成三角形，我们知道需要满足以下条件：

1. 任意两边之和大于第三边

2. 任意两边之差小于第三边

那么我们先将数组排序，可以固定一条边（此边最小），将这个数右边的数作为一个区间，借助双指针来判断这三个数是否能够组成三角形，代码如下

class Solution { public: int triangleNumber(vector<int>& nums) { sort(nums.begin(), nums.end()); int count = 0; int n = nums.size(); for (int i = n-1; i >= 2; i--) { int left = 0; int right = i-1; while (left < right) { if (nums[left] + nums[right] > nums[i]) { count += right - left; right--; } else { left++; } } } return count; } };

6. 和为s的两个数

题目链接：LCR 179. 查找总价格为目标值的两个商品 – 力扣（LeetCode）

解析：分析题目后，我们可以使用双指针从数组的两端向中间寻找，由于数组是升序的，因此当结果 < target时，left++即可，当结果> target时，right–即可，代码如下

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

7. 三数之和

题目链接：15. 三数之和 – 力扣（LeetCode）

解析：这道题要求找到三数之和为0的三元组，那么我们可以先将数组排序，每次固定一个最小的数（最左端），在它右边的剩余区间中借助双指针找到符合nums[left] + nums[ight] == nums[min]的数，代码如下

class Solution { public: vector<vector<int>> threeSum(vector<int>& nums) { // 借助set去重 set<vector<int>> res; sort(nums.begin(), nums.end()); int n = nums.size(); for (int i = 0; i < n-2; i++) { int left = i+1; int right = n-1; while (left < right) { if (nums[left] + nums[right] < -nums[i]) left++; else if (nums[left] + nums[right] > -nums[i]) right--; else { vector<int> tmp = {nums[i], nums[left++], nums[right--]}; res.insert(tmp); } } } vector<vector<int>> ret; for (auto& e : res) ret.push_back(e); return ret; } };

8. 四数之和

题目链接：18. 四数之和 – 力扣（LeetCode）

解析：对于四数之和我们可以采取和三数之和类似的处理方法，即先将数组排序，固定一个最小的数（最左端数），在剩下的区间内再去固定另一个最小值，再借助双指针寻找并判断四数是否满足对应关系，代码如下

class Solution { public: vector<vector<int>> fourSum(vector<int>& nums, int target) { sort(nums.begin(), nums.end()); set<vector<int>> res; int n = nums.size(); for (int i = 0; i < n - 3; i++) { for (int j = i+1; j < n-2; j++) { int left = j+1; int right = n-1; while (left < right) { int a = nums[i]; int b = nums[j]; int c = nums[left]; int d = nums[right]; long long t_left = nums[left] + nums[right]; long long t_right = target; t_right -= nums[i]; t_right -= nums[j]; if (t_left < t_right) left++; else if (t_left > t_right) right--; else { vector<int> tmp = {a,b,c,d}; res.insert(tmp); left++; right--; } } } } vector<vector<int>> ret; for (auto& e : res) ret.push_back(e); return ret; } };

免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/110422.html

算法——双指针

1. 什么是双指针算法？

2. 双指针算法的常见形式