❤️写在开头：
😣😣封校实在是无聊，想起来博客也断更好久了，为了不荒废青春，同时总结一些最近刷的算法题，就决定整理一下思路，结合力扣上的题，写一写双指针的用法。
当然了，这个主题也不是瞎选的，因为双指针真的是太强了，一次又一次地刷新我的认知。😂😂
目录：
🦝🦝一，什么是双指针 🐸🐸二，对撞指针 👀👀👀 看例题👀👀 💻💻代码实现💻💻 🐇🐢三，快慢指针 👀👀👀 看例题👀👀 💻💻代码实现💻💻 🦄🦄四，滑动窗口 👀👀👀 看例题👀👀 💻💻代码实现💻💻 ❤️❤️结尾🦝🦝一，什么是双指针
所谓双指针，指的是在遍历对象的过程中，不是普通的使用单个指针进行访问，而是使用两个相同方向（快慢指针）或相反方向（对撞指针）的指针进行扫描。
这里的指针意思是比较广的，可以是定义的变量，索引，可迭代对象等，并不仅仅指c语言中指向地址的指针。
细分的话，双指针可以分为好几个类型：
1，对撞指针
2，快慢指针
3，滑动窗口
接下来会结合例题详细讲解 。
🐸🐸二，对撞指针
对撞指针什么意思呢？
没错，就是字面意思，分别设置两个指针，一左一右，分别向中间逼近。
👀👀👀 看例题👀👀
反转字符串
难度：简单
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
s的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
示例 1：
输入：s = ["h","e","l","l","o"] 输出：["o","l","l","e","h"]示例 2：
输入：s = ["H","a","n","n","a","h"] 输出：["h","a","n","n","a","H"]
相信聪明的小伙伴立马就想到了reverse,哈哈😂
面试官：这题怎么说。
我：reverse
面试官：滚！
我们在练习算法的时候，可以多思考一下它的实现原理，这样有助于我们对算法的理解，以后才能活学活用，每次直接调用库函数，实在是偷懒。😓😓😓
那么这个题的思路是什么呢，我们可以设置左右两个指针，只需循环的对s[i]和s[j]进行交换，就可以实现整体的反转。
💻💻代码实现💻💻：
class Solution {
public:
void reverseString(vector& s) {
for (int i=0,j=s.size()-1;i 链接：力扣
🐇🐢三，快慢指针
快慢指的是移动速度的快慢，快指针移动两步，慢指针移动一步
用途：
1，判断单链表是否存在环
2，寻找循环链表的入口
3，寻找链表的中间节点
4，判断两个链表是否相交
👀👀👀 看例题👀👀
链表的中间节点
难度：简单
给定一个头结点为
head的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。
示例 1：
输入：[1,2,3,4,5] 输出：此列表中的结点 3 (序列化形式：[3,4,5]) 返回的结点值为 3 。 (测评系统对该结点序列化表述是 [3,4,5])。 注意，我们返回了一个 ListNode 类型的对象 ans，这样： ans.val = 3, ans.next.val = 4, ans.next.next.val = 5, 以及 ans.next.next.next = NULL.示例 2：
输入：[1,2,3,4,5,6] 输出：此列表中的结点 4 (序列化形式：[4,5,6]) 由于该列表有两个中间结点，值分别为 3 和 4，我们返回第二个结点。
这题的思路是什么呢，很简单
快指针q每次走2步，慢指针p每次走1步，当q走到末尾时p正好走到中间。
💻💻代码实现💻💻：
class Solution {
public ListNode middleNode(ListNode head) {
ListNode p = head, q = head;
while (q != null && q.next != null) {
q = q.next.next;
p = p.next;
}
return p;
}
}链接： 力扣
🦄🦄四，滑动窗口
定义：滑动窗口算法是在给定特定窗口大小的数组或字符串上执行要求的 *** 作。
用人话说出来就是，解决一些连续区间的问题，通过不断地对一段连续区间进行裁剪，移动 *** 作，可以减少重复计算，从而降低时间复杂度。这个逻辑就类似于咱门平常见到的推拉窗一样。
哈哈，找一个典型的例子说一说吧
👀👀👀 看例题👀👀
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
示例 1：
输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
示例 2：输入：s1= "ab" s2 = "eidboaoo"
输出：false
先来分析，由于排列不会改变字符串中每个字符的个数，所以只有当两个字符串每个字符的个数均相等时，一个字符串才是另一个字符串的排列。
根据这一性质，我们可以记s1的长度为n,遍历s2中每个长度为n的子串，判断子串和s1中的每个字符的个数是否相等，若相等则说明该字串是s1的一个排列。
使用两个数组cnt1和cnt2，cnt1统记s1中各个字符的个数，cnt2统计当前遍历的子串中各个字符的个数。
由于需要遍历的子串长度均为n,我们可以使用一个固定长度为n的滑动窗口来维护cnt2。滑动窗口每向右滑动一次，就多统计一次进入窗口的字符，少统计一次离开窗口的字符。
然后判断cnt1 是否与 cnt2相等，相等则说明s2的子串是s1的一个排列。
💻💻代码实现💻💻：
class Solution {
public:
bool checkInclusion(string s1, string s2) {
int n = s1.length(), m = s2.length();
if (n > m) {
return false;
}
vector cnt1(26), cnt2(26);
for (int i = 0; i < n; ++i) {
++cnt1[s1[i] - 'a'];
++cnt2[s2[i] - 'a'];
}
if (cnt1 == cnt2) {
return true;
}
for (int i = n; i < m; ++i) {
++cnt2[s2[i] - 'a'];
--cnt2[s2[i - n] - 'a'];
if (cnt1 == cnt2) {
return true;
}
}
return false;
}
};
链接：力扣
❤️❤️结尾：
为了能直观的感受双指针算法的实现原理，我选的都是一些典型，简单的例题，当然，因为接触算法的时间还比较短，很多地方理解的还不够全面，希望小伙伴们能够指正，一起进步。
关于双指针还有很多很经典的例题，文章最后也放一个比较好的题，感兴趣的小伙伴可以看一看，鲁迅先生说过：趁热打铁，多是一件美逝啊。
链接：力扣
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）