「算法刷题」双指针法（快慢指针法）

Posted on 2021-10-09 Edited on 2024-02-02

一、顺序结构中的双指针法

顺序结构：这里主要指的是数组或字符串。

（1）普通数组

slow指向当前所需元素数组的下一个空位。返回值为slow时，slow就代表目标数组的长度。

题目简述	关键点	解题思路	力扣题目	相关链接
删除数组中的某类元素	同向移动，快慢指针同时出发；	slow：指向当前所需元素数组的下一个空位。fast：遍历数组。如果快指针遇到目标值则快指针直接跳过它一步，慢指针不动，如果快指针没有遇到目标值则将自己手中的数交给慢指针，然后各自前进一步。	27 移除元素（简单难度）	https://leetcode-cn.com/problems/remove-element/
移动数组中的某类元素到开头或者末尾	同向移动，快慢指针同时出发；	如果快指针遇到目标值则快指针直接跳过它一步，慢指针不动，如果快指针没有遇到目标值则将自己手中的数和慢指针交换，然后各自前进一步。	283 移动零（简单难度）	https://leetcode-cn.com/problems/move-zeroes/

（2）有序数组

无序数组可以直接使用sort()函数排序后变成有序数组。sort(nums.begin(),nums.end())

题目简述	关键点	解题思路	力扣题目	相关链接
删除有序数组中的重复元素	同向移动，快指针先行一步，每次不断比较两个指针上的数是否相同。	一个指针（fast）从头到尾遍历，另一个（slow）始终指示当前没有重复的元素数组的下一个空位置；相同则快指针直接跳过去多行一步，不相同则快指针将手中的数交给慢指针，然后快慢指针同时前进一步；（这时慢指针指的是当前没有重复元素的最后一个*：注意返回值是slow+1。）	26 删除排序数组中的重复项（简单难度）	https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/
求有序数组中的众数（可能不止一个）	同向移动，快指针先行一步，每次不断比较两个指针上的数是否相同。	相同则频率计时器+1，不相同则频率计时器设为0；每次检查频率计时器是否超过最大计数，超过则记录当前快指针上的数为众数。vector数组排序：sort(nums.begin(),nums.end())	169 多数元素（中等难度）	https://leetcode-cn.com/problems/majority-element/
将有序数组中每个元素平方后再排序	反向移动，左指针和右指针同时出发，每次比较左指针和右指针手上的数的平方；	如果左指针手中数的平方更大则移动起始指针，如果末尾指针手中的数更大则移动末尾指针；当起始指针大于末尾指针时循环结束。（有序数组平方数组平方的最大值就在数组的两端，所以排序需要不断比较数组两端的数）	977 有序数组的平方（简单难度）	https://leetcode-cn.com/problems/squares-of-a-sorted-array/

169 多数元素（中等难度）

1、排序法

众数是指在数组中出现次数大于⌊ n/2 ⌋ 的元素。先将nums排序，，然后返回中间元素的值即可（众数的个数大于一半，排好序的nums中间元素一定是众数）。

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        sort(nums.begin(),nums.end());
        return nums[nums.size()/2];
    }
};

2、摩尔投票法思路

候选人(cand_num)初始化为nums[0]，票数count初始化为1。
当遇到与cand_num相同的数，则票数count = count + 1，否则票数count = count - 1。
当票数count为0时，更换候选人，并将票数count重置为1。
遍历完数组后，cand_num即为最终答案。

为何这行得通呢？
投票法是遇到相同的则票数 + 1，遇到不同的则票数 - 1。
且“多数元素”的个数> ⌊ n/2 ⌋，其余元素的个数总和<= ⌊ n/2 ⌋。
因此“多数元素”的个数 - 其余元素的个数总和的结果肯定 >= 1。
这就相当于每个“多数元素”和其他元素两两相互抵消，抵消到最后肯定还剩余至少1个“多数元素”。

无论数组是1 2 1 2 1，亦或是1 2 2 1 1，总能得到正确的候选人。

作者：gfu
链接：https://leetcode-cn.com/problems/majority-element/solution/3chong-fang-fa-by-gfu-2/
来源：力扣（LeetCode）

代码如下：

class Solution {
public:
    int majorityElement(vector<int>& nums) {
        int cand=nums[0],count=1;
        for(int i=1;i<nums.size();i++){
            if(cand==nums[i]){
                count++;
            }
            else if(--count==0){
                cand=nums[i];
                count=1;
            }
        }
        return cand;
    }
};

二、非顺序结构中的双指针法

这里的非顺序结构主要指的是：链表或二叉树。

1、链表

链表删除某个元素的模板：

1、创建头结点和当前结点

2、删除结点

3、还原真实头结点，返回。

ListNode* removeElements(ListNode* head, int val) {
        //新建虚拟头结点
        ListNode * myHead = new ListNode(0);
        myHead->next=head;
        //循环检查链表的当前节点的下一节点
        ListNode* cur=myHead;//当前节点（一定不为空）
        while (cur->next != NULL) {
            if(cur->next->val == val) {
                cur->next = cur->next->next;//删除下一节点
            } else {
                cur = cur->next;//更新当前节点为下一节点
            }
        }
        //还原真实头结点
        head = myHead->next;
        return head;
    }

（1）链表的删除操作

有序链表中删除一个节点cur需要其前一个节点pre->next=cur->next; 所以其天生需要节点的先后关系。

所以在执行删除操作时，一般就需要(头结点)

题目简述	关键点	解题思路	力扣题目	相关链接
删除链表中的某类元素（简单难度）	虚拟头结点；链表的循环操作和节点的删除操作	同向移动，快指针从头结点先行一步，每次判断快指针是否符合删除条件，若符合则删除快指针并且重新为快指针赋值；否则则快指针和慢指针都前进一步。	203 移除链表元素（简单难度）	https://leetcode-cn.com/problems/remove-linked-list-elements/
删除链表的倒数第N个节点（中等难度）	快指针先走N步之后进行判断	同向出发，快指针从头结点先行N步，如果此时快指针不存在则直接返回，若存在则快指针和慢指针（从头结点）同时出发，当快指针不存在时删除慢指针之后的一个节点。	19 删除链表的倒数第N个节点（中等难度）	https://leetcode-cn.com/problems/remove-nth-node-from-end-of-list/

19.删除链表的倒数第n个结点

（1）假设链表长度为m+n。

fast、slow开始指向虚拟头结点。

1、fast先走n步

2、fast和slow同时走，直到fast指向链表的最后一个。

则slow走了m步。

（2）链表的删除操作，需要得到目标结点的前一个结点。

所以

1、fast先走n+1步。

2、fast和slow同时走，直到fast指向链表的最后一个的下一个位置：NULL。

则slow走了m-1步，在倒数第n个结点前。

（2）链表的反转操作

题目简述	关键点	解题思路	力扣题目	相关链接
将一个链表全部反转过来	相邻节点之间的反转操作	同向移动，快指针从头结点先行一步；每次移动快节点和慢节点都进行一次反向	206 反转链表（简单难度）	https://leetcode-cn.com/problems/reverse-linked-list/
将一个链表中的[left,right]区域反转过来		慢指针从虚拟头结点出发找到第left个节点，然后快指针从慢指针的后一个节点出发，共同前进找到第right个节点	92 反转链表II（中等难度）	https://leetcode-cn.com/problems/reverse-linked-list-ii/
		根据快慢指针找到中点；反转后半段；比较前后两端节点值	234 回文链表（简单难度）	https://leetcode-cn.com/problems/palindrome-linked-list/

206、反转链表

1、保存后面链表

2、断开指针

3、重新规划pre、cur

234、回文链表

1、慢指针走一步，快指针走两步

2、pre记录慢指针的前一个，用来分割链表，如果链表长度为奇数，则后半部分多一个结点。

3、将后半部分反转，得cur2，前半部分为cur1.

4、按照cur1的长度，比较cur1和cur2的节点数值。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        ListNode* slow=head;
        ListNode* fast=head;
        ListNode* pre=head;
        
        //慢指针走一步，快指针走两步
        while(fast && fast->next){
            pre=slow;
            slow=slow->next;
            fast=fast->next->next;
        }
        
        //pre断开链表
        pre->next=NULL;
        ListNode* cur1=head;
        //反转cur2
        ListNode* cur2=reverselist(slow);
        //按照cur1的长度，比较cur1，cur2
        while(cur1){
            if(cur1->val!=cur2->val){
                return false;
            }
            cur1=cur1->next;
            cur2=cur2->next;
        }
        return true;

    }
    ListNode* reverselist(ListNode* head){
        ListNode* cur=head;
        ListNode* temp=head;
        ListNode* pre=NULL;
        while(cur){
            //保存后面链表
            temp=cur->next;
            //断开原链表
            cur->next=pre;
            //重新规划pre，cur
            pre=cur;
            cur=temp;
        }
        return pre;
        
    }
};