双指针
双指针是出现常用的一种解题方法。两个指针就像兄弟一般完美配合，不论是左右指针还是快慢指针，都可以达到非常好的效果。
数组下的双指针
对于数组来说，在要求对重复元素移除等需要原地移除（也就是在原数组身上做改变，而不新建数组）
移除元素多种写法
先来看一道简单题：
leetcode 27 移除元素
原地移除所有数值等于val的元素。
这时我们就可以定义两个指针，一个快指针一个慢指针。
快指针，就是一直向前走的那一个。而慢指针则是遇到需要处理的情况才动身的那一个。
比如[0,1,2,2,3]，val=2
快指针fast先判断，如果当前指向的元素不是val，那么把这个值给慢指针slow，然后fast走一步，slow走一步。
是val那么slow就不走。（这样做是为了跳过val，同时又能把val之后的值覆盖到val的位置）
我们先用最通俗的写法：
int removeElement(vector<int>& nums, int val) {
int slow=0,fast=0;
while(fast!=nums.size()){
if(nums[fast]!=val){
nums[slow]=nums[fast];
fast++;
slow++;
}
else
fast++;
}
return slow;
}
说一下返回值为什么是slow。最后要求返回长度，看上去slow是从0开始的，应该+1。但实际上我们在最后判断时让slow++了，所以就不用+1了。
这里可以进一步简化为：
int removeElement(vector<int>& nums, int val) {
int slow=0,fast=0;
while(fast!=nums.size()){
if(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}
fast++;
}
return slow;
}
当然我们也可以把fast写到for循环里：
for(fast=0;fast<nums.size();fast++){
if(nums[fast]!=val){
nums[slow]=nums[fast];
slow++;
}
}
删除排序数组的重复值
这也是一道双指针问题，只是需要多思考一下赋值的过程
leetcode 26 删除有序数组中的重复项
比如[0,1,1,1,2,2,3,3]，我们也需要fast和slow来帮忙。
但这种情况下没有val，所以需要fast和slow前后错开一位来判断是不是遇到了重复的元素。
int removeDuplicates(vector<int>& nums) {
int fast=0,slow=0;
while(fast!=nums.size()){
if(nums[fast]!=nums[slow]){
slow++;
nums[slow]=nums[fast];
}
fast++;
}
return slow+1;
}
和上一题最大的区别在于：这里是先给slow++再赋值的（这个过程画个图很好理解），因为是去重，所以需要保留一个元素。由于最后slow的位置就是数组下标，所以返回长度要+1
移动零
也是一道双指针的简单题目：
leetcode 283 移动零
把所有的零移动到后面，保持非零元素的顺序不变。
我们可以理解为先把零移除了，再把剩下的元素都变为零。
void moveZeroes(vector<int>& nums) {
int slow=0,fast=0;
while(fast<nums.size()){
if(nums[fast]!=0){
nums[slow]=nums[fast];
slow++;
}
fast++;
}
for(int i=slow;i<nums.size();i++){
nums[i]=0;
}
}
理，这里的slow已经+1了，所以赋值0的时候就是从下标slow开始的。
有序数组的平方
也有一些比较数学的问题，用双指针会方便很多。
leetcode 977 有序数组的平方
给一个数组[-4,-1,0,3,10]，平方后排序，得[0,1,9,16,100]。当然也可以直接平方后排序，这里我们说一下双指针得方法。
**核心思想为：**最大的数不是在最左边就是最右边。（因为存在负数变为正的情况）
我们定义两个指针，从两端开始比较并填入平方的值即可。
vector<int> sortedSquares(vector<int>& nums) {
vector<int>ans(nums.size(),0);//这个不太好原地覆盖了，需要定义一个新数组
int n=nums.size()-1;
int left=0;
int right=nums.size()-1;
while(left<=right){//需要等于才能把最后一个值填入
if(nums[left]*nums[left]<nums[right]*nums[right]){
ans[n--]=nums[right]*nums[right];
right--;
}
else{
ans[n--]=nums[left]*nums[left];
left++;
}
}
return ans;
}
字符串的双指针
字符串其实本质上和数组大同小异。这有一道字符串的双指针题目可以用来锻炼问题分析能力。
leetcode 844 比较含退格的字符串
题目中增加了一个退格字符#，也就是可以把#前面的字符删掉。
为了方便使用双指针的解法，我们可以倒着遍历字符串，这样在遇到#时记录下来，然后当#数量大于0时跳过前面的字符（也相当于删除），再去比较。
（代码第一眼看上去有些长，结合注释其实很好理解）
bool backspaceCompare(string s, string t) {
int i=s.size()-1;//字符串s的长度
int j=t.size()-1;//字符串t的长度
int skipS=0,skipT=0;//分别记录s和t中退格字符#的个数
while(i>=0||j>=0){//保证至少有一个没有出界，有可能有一个字符串已经遍历完了
while(i>=0){
if(s[i]=='#'){//如果是退格符，记录，继续向前
skipS++;
i--;
}
else if(skipS>0){//如果不是退格符但是现在退格符数量不为0，可以删一个。当然多个#也可以删多个，比如ab##就为空
skipS--;
i--;
}
else
break;
}
while(j>=0){//同理，统计字符串t的退格
if(t[j]=='#'){
skipT++;
j--;
}
else if(skipT>0){
skipT--;
j--;
}
else
break;
}
//统计完退格，开始进入正式比较
if(i>=0&&j>=0){//都在界内，如果字符不相等，那说明不一样
if(s[i]!=t[j])
return false;
}
else if(i>=0||j>=0)//如果有一个出界了，那么说明不相等了。当然如果两个都出界那么就都为空，是相等的。
return false;
//继续往前遍历
i--;
j--;
}
return true;
}
链表中的双指针
链表中双指针的应用也非常多，可以巧妙地解决一些问题。
链表的环
链表最常见的就是判断环的一些问题。
leetcode 141 环形链表
判断链表有没有环的关键在于：尾指针是不是指向null
这时候就可以用fast和slow来遍历。fast每次走两步，slow每次走一步，如果fast会和slow相遇，那么说明有环。
bool hasCycle(ListNode *head) {
ListNode *fast,*slow;
fast=slow=head;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(fast==slow)
return true;
}
return false;
}
环的入口
上一道题的升级版就是这道判断环的入口。
leetcode 142 环形链表2
其实环的入口有点数学性质在里面。如下面的推导所示：
slow每次走一步，fast每次走两步。
在他们相遇时，a+b就是slow走的距离，而a+2b+c就是fast走的距离。
这时他们之间有两倍关系，所以可以得到a与c相等。
这个时候我们让一个和slow一样的指针从链表头走，当他们相遇时，就是入口的位置。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-x6GjuydV-1647865949949)(…/…/…/Downloads/图片 2022-03-11 10-20-18.png)]
ListNode *detectCycle(ListNode *head) {
ListNode *fast,*slow;
fast=slow=head;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
if(slow==fast)
break;
}
//以上部分是让fast和slow相遇
if(fast==NULL||fast->next==NULL) return NULL;
//以下部分是利用a=c求环的入口
slow=head;
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}
这里需要注意的是，我们前面的推论是在有环时才成立的。但是是否有环需要判断（也就是前面说的如果没环那么最后是NULL结尾）
找链表中的一些点
还有一类寻找链表的特殊点的题目，也是双指针的发挥空间。
leetcode 876 寻找链表的中点
寻找一个链表的中点，我们发现这里如果是偶数结点的话那么返回的是中间靠后的结点。
利用双指针可以很好地解决。fast一次走两步，slow一次走一步。当fast走到结尾的时候，slow刚好是这里要求的中点。
ListNode* middleNode(ListNode* head) {
ListNode *fast,*slow;
fast=slow=head;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next->next;
slow=slow->next;
}
return slow;
}
还有这道：
leetcode 19 删除链表的倒数第N个节点
举个例子，比如1-2-3-4-5-6，删除倒数第三个也就是4
我们可以让fast指针走n步，也就是走3步，到达4
slow从头开始，然后fast和slow同时走，这样fast走2步到达尾部时，slow也走2步到了3，next就是需要删除的结点。
其实就是一个数学性质的小技巧。
ListNode* removeNthFromEnd(ListNode* head, int n) {
ListNode *fast,*slow;
fast=slow=head;
while(n>0){
fast=fast->next;
n--;
}
if(fast==NULL)return head->next;
while(fast!=NULL&&fast->next!=NULL){
fast=fast->next;
slow=slow->next;
}
slow->next=slow->next->next;
return head;
}
需要注意，如果倒数第n个正好是头结点，那么fast就会走到NULL，所以这种情况需要单独判断。
（关于链表的部分还是建议使用虚头结点）
还有很多双指针的例子，我们在后面的具体类型归纳中深入研究。
|