双指针算法

双指针算法

常见的双指针有两种形式，⼀种是对撞指针，⼀种是左右指针。

双指针算法指的是在遍历对象的过程中，不是使用单个指针，而是使用两个相同方向的（快慢指针）或者相反方向的（对撞指针）指针进行扫描，从而达到相应的目的。

这里的指针并不是实际意义上的int*，而是像数组的下标等。

• 快慢指针是指两个指针从同一侧开始遍历数组，将这两个指针分别定义为快指针（fast）和慢指针（slow），两个指针移动的速度不同，直到两个指针所指位置相等（或其他条件），比如：fast++,fast++,slow++

• 对撞指针是指在有序数组中，将指向的最左侧定义为左指针(left)，最右侧定义为右指针(right)，然后从两头向中间进行数组遍历。

移动零

题目链接：Leetcode283. 移动零

思路
使用同向的两个指针，
cur用来遍历数组，
dest已经处理区间内，非零元素的最后一个位置
通过上述两个指针我们就可以将区间分为三个部分
[0, dest]、[dest + 1, cur - 1]、[cur, nums.size() - 1]
分别是，非零元素、零元素、未处理
步骤

1. 初始化两个指针cur = 0,dest = -1
2. 遍历当前数组，如果当前位置不为零，交换cur和dest的下一个位置，dest++,cur++；如果为零，cur++
3. 继续遍历，直到数组遍历完毕。

C++代码

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

复写零

题目链接：Leetcode1089. 复写零

思路

• 先找到最后一个“复写”的数
• 从后向前复制零

步骤

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

• 初始化cur = 0,dest = -1
• 判断cur位置的值；
• 决定dest移动一步还是两步；
• 判断dest是否到结束的位置；
• cur++;
  需要判断一下边界

2. 从后向前完成复写操作；

C++代码

class Solution {
public:void duplicateZeros(vector<int>& arr) {//找最后一个复写位置int n = arr.size();int cur = 0, dest = -1;while(cur < n){if(arr[cur] == 0){dest++, dest++;}else{dest++;}if(dest >= n - 1) break;cur++; }//处理边界if(dest == n){arr[n - 1] = 0;cur--; dest--, dest--;}//从后先前完成复写while(cur >= 0){if(arr[cur]) arr[dest--] = arr[cur--];else{arr[dest--] = 0;arr[dest--] = 0;cur--;}}}
};

快乐数

题目链接：Leetcode202. 快乐数

思路
对于本题不管是否为快乐数，该数最终必定进入一个循环。进入循环体的入口结点数字为 1，则该数为快乐数，否则不是快乐数。所以本题等价于求有环链表的入环节点
步骤
快慢指针

• 定义一个next数组用来计算n的每位数字的平方和
• 使用两个指针，fast和slow
• slow每次计算一次，也就是走一步；fast每次计算两次，也就是走两步；
• 如果最后进入一个循环那么最终一定会相遇，并且slow == 1，则是快乐数；如果相遇但```slow != 1````，则不是快乐数；

C++代码

class Solution {
public:int next(int x){int sum = 0;while(x){int t = x % 10;sum += t * t;x /= 10;}return sum;}bool isHappy(int n) {int slow = n;int fast = next(n);while(slow != fast){slow = next(slow);fast = next(next(fast));}return slow == 1;}
};

盛最多水的容器

题目链接：盛最多水的容器

思路
枚举所有情况但时间复杂度O(N^2)；我们使用对撞指针，不断更新较低的一方面积更大；
步骤

• 初始化left 和right 来定义起始和终止位置，area来定义所围面积；
• while（left < right ）为循环条件，计算left和right之间的面积，比较后更新答案ans

C++代码

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

有效三角形的个数

题目链接：有效三角形的个数

补充：

• 三个数是否能够构成三角形a,b,c的条件为a + b > c, a + c > b, b + c > a
• 若三个数有序，即a <= b <= c，则仅需判断一次即，a + b > c

思路

• 暴力枚举所以三元组，时间复杂度太高O(N^3)
• 利用数组有序

步骤

• 排升序
• 固定最大的数c作为最大的边下标为即i = n-1，定义下标left = 0和right = i - 1
• 判断是否构成三角形nums[left] + nums[right] > nums[i]；若成立即(nums[left], nums[right], nums[i])是一组解，此时因为数组排序，所以(nums[left]~nums[right - 1]和nums[right])和nums[i]是一组解，res += (right - left)为当前的解
• 若成立，下一步寻找更小的组，即right--；
• 若不成立，则加大边长，即left++；

C++代码

class Solution 
{
public:int triangleNumber(vector<int>& nums) {int res = 0;sort(nums.begin(), nums.end());int 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]) {res += (right - left);right--;}else{left++;}}}return res;}
};

和为s的两个数字

题目链接：和为s的两个数字

思路

• 暴力枚举所有二元组
• 利用数组升序，使用双指针

步骤

• 初始化left , right定义起始和终止位置；
• 循环条件while(left < right)计算left和right位置的和sum，
• if(sum > target) right--
• if(sum < target) left++
• if(sum == target) return {price[letf], price[right]}
• 循环结束未返回答案，则return {};

C++代码

class Solution 
{/*- 初始化left , right定义起始和终止位置；- 循环条件```while(left < right)```计算```left和right```位置的和```sum```，- ```if(sum > target) right--```- ```if(sum < target) left++```- ```if(sum == target) return {nums[letf], nums[right]}```- 循环结束未返回答案，则```return {};```*/
public:vector<int> twoSum(vector<int>& price, int target) {int left = 0, right = price.size() - 1;while(left < right){int sum = price[left] + price[right];if(sum > target) right--;if(sum < target) left++;if(sum == target) return {price[left], price[right]};}return {};}
};