双指针法的原理

双指针法相对于暴力解法的优点有以下几点

• 暴力遍历的时间复杂度会比较高
• 双指针法利用两个指针进行遍历完成双层循环所做的事情

双指针一般有两种方法 同向指针，双向指针

第一题 leetcode 27 移除元素

题目描述

题目分析

采用暴力遍历可以得出结果，但是时间复杂度会比较高
本题中采用左右指针的做法 左指针实际是记录真实数组的下标，右指针进行遍历查找非目标指

代码如下所示

class Solution {
public:int removeElement(vector<int>& nums, int val) {if(nums.size()==0){return 0;}int left = 0;int right = nums.size() - 1;while(left<=right){if(nums[left]!=val){left++;continue;}if(nums[right]==val){right--;continue;}// 排除以上的情况进行交换nums[left] = nums[right];left++;right--;}return left;}
};

第二题 leetcode 26 删除重复元素

题目描述

分析

此题需要删除元素
那么用快指针进行遍历查找非重复元素
慢指针在上一个非重复元素处

代码实现

class Solution {
public:int removeDuplicates(vector<int>& nums) {int slow = 0;if(nums.size()==1){return 1;}for(int fast=1; fast<nums.size(); fast++){if(nums[slow]!=nums[fast]){nums[++slow] = nums[fast];}}return ++slow;}
};

第三题 leetcode 283移动0

题目描述

代码注释看

class Solution {
public:void moveZeroes(vector<int>& nums) {int slow = 0;// 慢指针记录非0数// 快指针进行遍历查找0 遇到0跳过 非0进行移动for(int fast=0; fast<nums.size(); fast++){if(nums[fast]!=0){	// slow++是为了保持记录nums[slow++] = nums[fast];}}for(int i=slow; i<nums.size(); i++){nums[i] = 0;}}
};

第四题 leetcode 844 比较含退格的字符串

题目描述

题目分析

这个问题有多种思路
下面的方法是其中的一种思路

1. 对每个字符串进行从后遍历计算#的个数 遇到非#就-1
2. 遍历结束得到剩下的下标
3. 再次进行遍历比对剩下的字符

class Solution {
public:bool backspaceCompare(string s, string t) {int t_remin = 0;int s_remin = 0;int i = s.size() - 1;int j = t.size() - 1;while(1){while(i>=0){if(s[i]=='#'){s_remin++;}else{if(s_remin>0){s_remin--;}else{break;}}i--;}while(j>=0){if(t[j]=='#'){t_remin++;}else{if(t_remin>0){t_remin--;}else{break;}}j--;}if(i<0 || j<0){break;}if(s[i]!=t[j]){return false;}i--;j--;}if(i<0 && j<0){return true;}return false;}
};