双指针算法详解（快慢指针、对撞指针、滑动窗口）

今天药忘吃喽~ 2022-12-24 10:58 203阅读 0赞

**目录**

双指针

快慢指针

例题

思路

代码

对撞指针

例题

思路

代码

滑动窗口

例题

思路

代码

--------------------

# 双指针 #

双指针比较灵活，可以大大降低时间复杂度，可用在数组，单链表等数据结构中。

快慢指针：一快一慢，步长一大一小。例如，是否有环问题（看慢指针是否能追上快指针），单链表找中间节点问题（快指针到单链表结尾，慢指针到一半）。

对撞指针：一左一右向中间逼近。

滑动窗口：类似计算机网络中的滑动窗口，一般是右端向右扩充，达到停止条件后右端不动，左端向右端逼近，逼近达到停止条件后，左端不动，右端继续扩充。

# 快慢指针 #

## 例题 ##

给定一个链表，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。

如果链表中存在环，则返回 true 。 否则，返回 false 。

进阶：

你能用 O(1)（即，常量）内存解决此问题吗？

示例 1：

![20201130204430445.png][]

输入：head = \[3,2,0,-4\], pos = 1  
输出：true  
解释：链表中有一个环，其尾部连接到第二个节点。

示例 2：

![20201130204446273.png][]

输入：head = \[1,2\], pos = 0  
输出：true  
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

![20201130204458112.png][]

输入：head = \[1\], pos = -1  
输出：false  
解释：链表中没有环。

提示：

链表中节点的数目范围是 \[0, 104\]  
    -105 <= Node.val <= 105  
    pos 为 -1 或者链表中的一个 有效索引 。

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/linked-list-cycle

### 思路 ###

设置一快一慢指针，如果快指针追上慢指针，则有环。如果快指针到达链表尾，说明无环。

### 代码 ###

/**
     * Definition for singly-linked list.
     * struct ListNode {
     *     int val;
     *     ListNode *next;
     *     ListNode(int x) : val(x), next(NULL) {}
     * };
     */
    class Solution {
    public:
        bool hasCycle(ListNode *head) {
            if(head==nullptr||head->next==nullptr)return false;
            ListNode * slow = head;
            ListNode * fast = slow->next;
            while(fast!=slow)
            {
                if(fast==nullptr||fast->next==nullptr)return false;
                slow = slow->next;
                fast = fast->next->next;
            }
            return true;
        }
    };

# 对撞指针 #

## 例题 ##

编写一个函数，以字符串作为输入，反转该字符串中的元音字母。

示例 1：

输入："hello"  
输出："holle"

示例 2：

输入："leetcode"  
输出："leotcede"

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/reverse-vowels-of-a-string

### 思路 ###

设置左右两个指针，从两侧指向元音字母，不相等时交换。如果两指针相撞（左右指针指向同一位置或左指针在右指针右侧），则停止。

### 代码 ###

class Solution {
    public:
        string yuan = "aeiouAEIOU";
        bool isYuan(char c)
        {
            for(auto a:yuan)
            {
                if(c==a)return true;
            }
            return false;
        }
        string reverseVowels(string s) {
            int n = s.length();
            if(n==0)return s;
            int left = 0;
            int right = n-1;
            while(left<right)
            {
                if(!isYuan(s[left])){left++;continue;};
                if(!isYuan(s[right])){right--;continue;};
                if(s[left]!=s[right])swap(s[left++],s[right--]);
                else
                {
                    left++;
                    right--;
                }   
            }
            return s;
        }
    };

# 滑动窗口 #

滑动窗口：有左右端点和长度，根据题目调整左右端点的位置进行滑动，也是一种特殊的双指针。

## 例题 ##

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

> 输入: s = "abcabcbb"  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

> 输入: s = "bbbbb"  
> 输出: 1  
> 解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

> 输入: s = "pwwkew"  
> 输出: 3  
> 解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。  
>      请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

> 输入: s = ""  
> 输出: 0
> 
> 提示：
> 
>     0 <= s.length <= 5 \* 104  
>     s 由英文字母、数字、符号和空格组成

来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters

### 思路 ###

窗口右端点向右扩展，停止条件：有了一个重复的字符或到达最后。右端点停止后，左端点收缩，停止条件：重复的字符不在滑动窗口内。

### 代码 ###

class Solution {
    public:
        int lengthOfLongestSubstring(string s) {
            int n = s.length();
            if(n==0) return 0;
            int left = 0;
            unordered_set<char> sub;
            int cnt = 0;
            for(int right=0;right<n;++right)
            {
                if(sub.find(s[right])==sub.end()) sub.insert(s[right]);
                else
                {
                    cnt = cnt>sub.size()?cnt:sub.size();
                    while(sub.find(s[right])!=sub.end())
                    {
                        sub.erase(s[left]);
                        ++left;
                    }
                    sub.insert(s[right]);
                }  
            }
            cnt = cnt>n-left?cnt:n-left;
            return cnt;
        }
    };

查找可以使用unorded\_map更快。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70][]

示意图如上，当然，代码是先去掉重复的，例如abc，a即将重复，先去除左边，直到去除了a，再添加a

更多数据结构与算法实现：[数据结构（严蔚敏版）与算法的实现（含全部代码）][Link 1]

有问题请下方评论，转载请注明出处，并附有原文链接，谢谢！如有侵权，请及时联系。

[20201130204430445.png]: /images/20221120/8507dc5272834d1685f96657a7dbe3fc.png
[20201130204446273.png]: /images/20221120/55383456a6ad4385a246d54dcaf888ae.png
[20201130204458112.png]: https://img-blog.csdnimg.cn/20201130204458112.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20201130213931692.PNG?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2xhZHlfa2lsbGVyOQ==,size_16,color_FFFFFF,t_70
[Link 1]: https://blog.csdn.net/lady_killer9/article/details/82695895