前言
这篇文章来讲双指针，这是一种在实际情况中十分常用的算法
正文
1、左右指针
左右指针主要来解决数组的问题，其中一些典型的应用场景以下会举例说明
一般来说，左右指针分别初始化在数组的左右两端，两指针同时向中间移动直至相遇
- 例题：二分搜索
int binarySearch(vector<int>& nums, int target) { int n = nums.size(); int p1 = 0; // 左指针初始化在数组左端 int p2 = n - 1; // 右指针初始化在数组右端 while (p1 <= p2) { int mid = p1 + (p2 - p1) / 2; if (nums[mid] == target) { return mid; } else if (nums[mid] < target) { p1 = mid + 1; // 左指针向右移动 } else if (nums[mid] > target) { p2 = mid - 1; // 右指针向左移动 } } return -1; }
例题：反转数组
void reverseArray(vector<int>& nums) { int n = nums.size(); int p1 = 0; // 左指针初始化在数组左端 int p2 = n - 1; // 右指针初始化在数组右端 while (p1 < p2) { swap(nums[p1], nums[p2]); p1++; // 左指针向右移动 p2--; // 右指针向左移动 } }
2、快慢指针
快慢指针主要来解决链表的问题，其中一些典型的应用场景以下会举例说明
一般来说，快慢指针都初始化在链表左端，两指针呈加性或乘性关系逐步向右端移动
- 例题：判断链表是否有环
bool hasCycle(ListNode* head) { ListNode* fast = head; // 快指针 ListNode* slow = head; // 慢指针 while ( fast != nullptr && fast -> next != nullptr ) { fast = fast -> next -> next; // 快指针每次走 2 步 slow = slow -> next; // 慢指针每次走 1 步 if (fast == slow) { return true; } } return false; } // 思路 // 假如链表有环，指针移动会陷入死循环，不能到达末尾 // 换句话说，如果指针能到达末尾，则表明链表不存在环 // 假如链表有环，快指针每次走两步，慢指针每次走一步 // 那么快慢指针必然会在环上的某个节点相遇
例题：如果链表无环，找出链表中点
ListNode* listMiddle(ListNode* head) { ListNode* fast = head; // 快指针 ListNode* slow = head; // 慢指针 while ( fast != nullptr && fast -> next != nullptr ) { fast = fast -> next -> next; // 快指针每次走 2 步 slow = slow -> next; // 慢指针每次走 1 步 } return slow; } // 思路 // 假如链表无环，快指针每次走两步，慢指针每次走一步 // 那么，当快指针到链表末尾时，慢指针刚好到链表中点
例题：如果链表无环，找出链表倒数第 n 个节点
ListNode* listLastK(ListNode* head, int n) { ListNode* fast = head; // 快指针 ListNode* slow = head; // 慢指针 while (n-- > 0) { // 快指针首先走 n 步 fast = fast -> next; } while (fast != nullptr) { fast = fast -> next; // 快指针每次走 1 步 slow = slow -> next; // 慢指针每次走 1 步 } return slow; } // 思路 // 首先，快指针先走 n 步，然后，快慢指针同时走 // 当快指针到达末尾，慢指针就是倒数第 n 个节点
例题：如果链表有环，找出环的起点
ListNode* listCycleS(ListNode* head) { ListNode* fast = head; // 快指针 ListNode* slow = head; // 慢指针 while ( fast != nullptr && fast -> next != nullptr ) { fast = fast -> next -> next; // 快指针每次走 2 步 slow = slow -> next; // 慢指针每次走 1 步 if (slow == fast) { break; } } slow = head; while (slow != fast) { fast = fast -> next; // 快指针每次走 1 步 slow = slow -> next; // 慢指针每次走 1 步 } return slow; } // 思路 // 假如链表有环，快指针每次走两步，慢指针每次走一步 // 那么快慢指针必然会在环上的某个节点相遇 // 如果这时让慢指针或快指针指向头节点，并让快慢指针同时逐步前进 // 那么当它们再次相遇时，就是环的起点 // 为什么呢 // 假设它们第一次相遇时，慢指针走了 n 步，快指针走了 2n 步 // 快指针多走的 n 步是从相遇点绕了环整数圈回到相遇点 // 设从环起点到相遇点是 m 步 // 对于慢指针而言，过去从头节点走了 n - m 步到达环起点，然后走了 m 步到达相遇点 // 对于快指针而言，未来从相遇点再走 n - m 步能到环起点，因为再走 n 步是到相遇点 // 如果现在把慢指针指向头节点，把快指针留在相遇点 // 那么，当它们同时再走 n - m 步，就能在环起点再次相遇
例题：如果链表有环，找出环的长度
int listCycleL(ListNode* head) { ListNode* fast = head; // 快指针 ListNode* slow = head; // 慢指针 while ( fast != nullptr && fast -> next != nullptr ) { fast = fast -> next -> next; // 快指针每次走 2 步 slow = slow -> next; // 慢指针每次走 1 步 if (slow == fast) { break; } } int clen = 0; fast = fast -> next -> next; // 快指针每次走 2 步 slow = slow -> next; // 慢指针每次走 1 步 clen += 1; while (slow != fast) { fast = fast -> next -> next; // 快指针每次走 2 步 slow = slow -> next; // 慢指针每次走 1 步 clen += 1; } return clen; } // 思路 // 假如链表有环，快指针每次走两步，慢指针每次走一步 // 那么快慢指针必然会在环上的某个节点相遇 // 这时快指针每次走两步，慢指针每次走一步 // 记录慢指针再次相遇快指针时的步数，就是环的长度 // 因为对于慢指针而言，刚好走过环的一圈回到相遇点 // 另外对于快指针而言，刚好走过环的两圈回到相遇点
3、滑动窗口
滑动窗口主要来解决子串的问题，其常规步骤及核心问题如下：
- 初始化左右指针，并确定窗口是左闭右闭区间还是左闭右开区间等等
- 右指针向右滑动，扩大窗口范围，直至窗口能够满足条件或不再满足条件，并更新数据
- 左指针向右滑动，缩小窗口范围，直至窗口不再满足条件或能够满足条件，并更新数据
- 重复上述两步骤，直至右指针到达字符串的末尾
滑动窗口典型的应用场景如下：
找出不含重复字符的最长子串 | leetcode3
给定一个字符串 s，找出其中不含重复字符的最长子串
解题思路：
在字符串 s 上使用滑动窗口，要求窗口不含重复字符
解题步骤：
初始化左右指针在字符串的开头，定义窗口为左闭右闭区间
右指针向右滑动，扩大窗口范围，直至窗口不再满足要求，更新辅助数据结构和答案
左指针向右滑动，缩小窗口范围，直至窗口能够满足要求，更新辅助数据结构
重复上述两步骤，直至右指针到达字符串的结尾
关键问题：
如何判断窗口是否包含重复字符？
维护一个辅助数据结构哈希集合，用于保存窗口包含的字符
当右指针移动、扩大窗口范围时，将其扫过的字符加入集合
当左指针移动、缩小窗口范围时，将其扫过的字符从集合中删除
class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); if (n == 0) { return 0; } // 初始化辅助结构 // 具体为哈希集合，用于保存窗口包含的字符 unordered_set<char> set; // 初始化左右指针 // 定义为左闭右闭区间 int p1 = 0; int p2 = -1; // 初始化答案的值 int ans = INT_MIN; // 滑动窗口主流程 while (true) { // 右指针向右滑动，扩大窗口范围，直至窗口包含重复字符，更新辅助数据结构 // 因为是求最大值，所以要在扩大窗口范围时更新答案 while (true) { p2++; if (p2 <= n - 1 && set.find(s[p2]) == set.end()) { ans = max(ans, p2 - p1 + 1); set.insert(s[p2]); } else { break; } } // 右指针到达字符串的结尾时停止 if (p2 >= n) { break; } // 左指针向右滑动，缩小窗口范围，直至窗口不含重复字符，更新辅助数据结构 while (true) { p1++; if (s[p1 - 1] != s[p2]) { set.erase(s[p1 - 1]); } else { break; } } } // 返回答案 return ans; } };
优化思路：
上述思路在移动左指针时，其实有很多不必要的操作
而通过优化辅助数据结构，可以使左指针一步移动到合适的位置
具体做法：
将辅助数据结构改变成哈希映射，用于记录窗口扫过的字符及其最后一次出现的位置
这样右指针遇到出现过的字符时，可以快速找到该字符上一次出现的位置，即左指针的更新位置
class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); if (n == 0) { return 0; } // 初始化辅助结构 // 具体为哈希映射，键为出现过的字符，值为其最后一次出现的位置 unordered_map<char, int> map; // 初始化左右指针 // 定义为左闭右闭区间 int p1 = 0; int p2 = -1; // 初始化答案的值 int ans = INT_MIN; // 滑动窗口主流程 while (true) { // 右指针向右滑动，扩大窗口范围，直至窗口包含重复字符，更新辅助数据结构 // 因为是求最大值，所以要在扩大窗口范围时更新答案 while (true) { p2++; if (p2 <= n - 1 && (map.find(s[p2]) == map.end() || map.find(s[p2]) -> second < p1)) { ans = max(ans, p2 - p1 + 1); map[s[p2]] = p2; } else { break; } } // 右指针到达字符串的结尾时停止 if (p2 >= n) { break; } // 左指针一步到位，缩小窗口范围，使得窗口不含重复字符，更新辅助数据结构 p1 = map[s[p2]] + 1; map[s[p2]] = p2; } // 返回答案 return ans; } };
找出覆盖给定字符的最短子串 | leetcode76
给定两个字符串 s 和 t，找出 s 中涵盖 t 所有字符的最短子串
解题思路：
在字符串 s 上使用滑动窗口，要求窗口涵盖字符串 t 的所有字符
解题步骤：
初始化左右指针在字符串的开头，定义窗口为左闭右闭区间
右指针向右滑动，扩大窗口范围，直至窗口能够满足要求，更新辅助数据结构
左指针向右滑动，缩小窗口范围，直至窗口不再满足要求，更新辅助数据结构和答案
重复上述两步骤，直至右指针到达字符串的结尾
关键问题：
根据上述思路，需要解决一个关键问题，即如何判断 s 中的窗口是否涵盖 t 中的所有字符？
维护两个哈希映射，分别用于保存 t 中的所有字符及其数量以及 s 窗口中的字符及其数量
然后根据哈希映射，判断 s 所对
class Solution { public: string minWindow(string s, string t) { int sLen = s.size(); int tLen = t.size(); if (sLen < tLen) { return ""; } // 初始化辅助结构 // 具体为哈希映射 unordered_map<char, int> sCnt; // 用于存放 s 窗口中的字符及其数量 unordered_map<char, int> tCnt; // 用于存放 t 中所有的字符及其数量 for (char & c: t) { tCnt[c]++; } // 初始化左右指针 // 定义为左闭右闭区间 int p1 = 0; int p2 = -1; // 初始化答案的值 int ansL = INT_MAX; int ans1; int ans2; // 滑动窗口主流程 while (true) { // 右指针向右滑动，扩大窗口范围，直至窗口包含字符串 t 所有字符 while (true) { p2++; sCnt[s[p2]]++; if (check(sCnt, tCnt) || p2 >= sLen) { break; } } // 右指针到达字符串的结尾时停止 if (p2 >= sLen) { break; } // 左指针向右滑动，缩小窗口范围，直至窗口不含字符串 t 所有字符 // 因为是求最小值，所以要在缩小窗口范围时更新答案 while (true) { if (ansL > p2 - p1 + 1) { ansL = p2 - p1 + 1; ans1 = p1; ans2 = p2; } sCnt[s[p1]]--; p1++; if (!check(sCnt, tCnt) || p1 > p2) { break; } } // 左指针到达字符串的结尾时停止 if (p1 >= sLen) { break; } } // 返回答案 return ansL == INT_MAX ? "" : s.substr(ans1, ansL); } // 判断 s 中的窗口是否涵盖 t 所有字符 bool check( unordered_map<char, int>& sCnt, unordered_map<char, int>& tCnt ) { for (auto & item: tCnt) { if (sCnt[item.first] < item.second) { return false; } } return true; } };
找出给定字符串的异位词子串 | leetcode438
给定两个字符串 s 和 p，找出 s 中所有 p 的异位词的开始索引
解题思路：
在字符串 s 上使用滑动窗口，要求窗口就是字符串 p 的异位词
这里隐含一个要求，那就是 s 中的窗口的长度和 p 的长度要是一样的
解题步骤：
初始化左右指针，定义窗口为左闭右闭区间，窗口长度等于异位词长度
将窗口向右移动，也即右指针向右移动一步、左指针向右移动一步，并更新辅助数据结构和答案
重复上述的步骤，直至右指针到达字符串的结尾
关键问题：
根据上述思路，需要解决一个关键问题，即如何判断 s 中的窗口是否等于 p 中的所有字符？
维护两个哈希映射，分别用于保存 p 中的所有字符及其数量以及 s 窗口中的字符及其数量
然后根据哈希映射，判断 s 所对应的哈希
class Solution { public: vector<int> findAnagrams(string s, string p) { int sLen = s.size(); int pLen = p.size(); if (sLen < pLen) { return vector<int>(); } // 初始化辅助结构 // 具体为哈希映射 unordered_map<char, int> sCnt; // 用于存放 s 窗口中的字符及其数量 unordered_map<char, int> pCnt; // 用于存放 p 中所有的字符及其数量 for (int i = 0; i < pLen; i++) { pCnt[p[i]]++; } // 初始化左右指针 // 定义为左闭右闭区间 int p1 = 0; int p2 = pLen - 1; for (int i = 0; i < pLen; i++) { sCnt[s[i]]++; } // 初始化答案的值 vector<int> ans; if (check(sCnt, pCnt)) { ans.emplace_back(0); } // 滑动窗口主流程 while (true) { // 右指针向右一步 p2++; sCnt[s[p2]]++; // 左指针向右一步 sCnt[s[p1]]--; p1++; // 右指针到达字符串的结尾时停止 if (p2 >= sLen) { break; } // 更新答案 if (check(sCnt, pCnt)) { ans.emplace_back(p1); } } // 返回答案 return ans; } // 判断 s 中的窗口是否就是 p 的异位词 bool check( unordered_map<char, int>& sCnt, unordered_map<char, int>& pCnt ) { for (auto & item: pCnt) { if (sCnt[item.first] != item.second) { return false; } } return true; } };
