这篇文章来讲双指针，这是一种在实际情况中十分常用的算法

1、左右指针

左右指针主要来解决数组的问题，其中一些典型的应用场景以下会举例说明

一般来说，左右指针分别初始化在数组的左右两端，两指针同时向中间移动直至相遇

• 例题：二分搜索

  int binarySearch(vector& 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& 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，找出其中不含重复字符的最长子串

  解题思路：

  1. 在字符串 s 上使用滑动窗口，要求窗口不含重复字符
     
     

  解题步骤：

  1. 初始化左右指针在字符串的开头，定义窗口为左闭右闭区间
  2. 右指针向右滑动，扩大窗口范围，直至窗口不再满足要求，更新辅助数据结构和答案
  3. 左指针向右滑动，缩小窗口范围，直至窗口能够满足要求，更新辅助数据结构
  4. 重复上述两步骤，直至右指针到达字符串的结尾
     
     

  关键问题：

  1. 如何判断窗口是否包含重复字符？

     维护一个辅助数据结构哈希集合，用于保存窗口包含的字符

     当右指针移动、扩大窗口范围时，将其扫过的字符加入集合

     当左指针移动、缩小窗口范围时，将其扫过的字符从集合中删除

  class Solution {
  public:int lengthOfLongestSubstring(string s) {int n = s.size();if (n == 0) {return 0;}// 初始化辅助结构// 具体为哈希集合，用于保存窗口包含的字符unordered_set 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;}
  };
  

  优化思路：

  1. 上述思路在移动左指针时，其实有很多不必要的操作

     而通过优化辅助数据结构，可以使左指针一步移动到合适的位置
     
     

  具体做法：

  1. 将辅助数据结构改变成哈希映射，用于记录窗口扫过的字符及其最后一次出现的位置

     这样右指针遇到出现过的字符时，可以快速找到该字符上一次出现的位置，即左指针的更新位置

  class Solution {
  public:int lengthOfLongestSubstring(string s) {int n = s.size();if (n == 0) {return 0;}// 初始化辅助结构// 具体为哈希映射，键为出现过的字符，值为其最后一次出现的位置unordered_map 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 所有字符的最短子串

  解题思路：

  1. 在字符串 s 上使用滑动窗口，要求窗口涵盖字符串 t 的所有字符
     
     

  解题步骤：

  1. 初始化左右指针在字符串的开头，定义窗口为左闭右闭区间
  2. 右指针向右滑动，扩大窗口范围，直至窗口能够满足要求，更新辅助数据结构
  3. 左指针向右滑动，缩小窗口范围，直至窗口不再满足要求，更新辅助数据结构和答案
  4. 重复上述两步骤，直至右指针到达字符串的结尾
     
     

  关键问题：

  1. 根据上述思路，需要解决一个关键问题，即如何判断 s 中的窗口是否涵盖 t 中的所有字符？

     维护两个哈希映射，分别用于保存 t 中的所有字符及其数量以及 s 窗口中的字符及其数量

     然后根据哈希映射，判断 s 所对应的哈希映射是否包含 t 所对应的哈希映射即可

  class Solution {
  public:string minWindow(string s, string t) {int sLen = s.size();int tLen = t.size();if (sLen < tLen) {return "";}// 初始化辅助结构// 具体为哈希映射unordered_map sCnt; // 用于存放 s 窗口中的字符及其数量unordered_map 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& sCnt,unordered_map& tCnt) {for (auto & item: tCnt) {if (sCnt[item.first] < item.second) {return false;}}return true;}
  };
  

• 找出给定字符串的异位词子串 | leetcode438

  给定两个字符串 s 和 p，找出 s 中所有 p 的异位词的开始索引

  解题思路：

  1. 在字符串 s 上使用滑动窗口，要求窗口就是字符串 p 的异位词

     这里隐含一个要求，那就是 s 中的窗口的长度和 p 的长度要是一样的
     
     

  解题步骤：

  1. 初始化左右指针，定义窗口为左闭右闭区间，窗口长度等于异位词长度
  2. 将窗口向右移动，也即右指针向右移动一步、左指针向右移动一步，并更新辅助数据结构和答案
  3. 重复上述的步骤，直至右指针到达字符串的结尾
     
     

  关键问题：

  1. 根据上述思路，需要解决一个关键问题，即如何判断 s 中的窗口是否等于 p 中的所有字符？

     维护两个哈希映射，分别用于保存 p 中的所有字符及其数量以及 s 窗口中的字符及其数量

     然后根据哈希映射，判断 s 所对应的哈希映射是否等于 p 所对应的哈希映射即可

  class Solution {
  public:vector findAnagrams(string s, string p) {int sLen = s.size();int pLen = p.size();if (sLen < pLen) {return vector();}// 初始化辅助结构// 具体为哈希映射unordered_map sCnt; // 用于存放 s 窗口中的字符及其数量unordered_map 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 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& sCnt,unordered_map& pCnt) {for (auto & item: pCnt) {if (sCnt[item.first] != item.second) {return false;}}return true;}
  };