双指针可以分为两类：快慢指针、左右指针。
快慢指针用于解决链表中的问题，如判断链表中是否有环；
左右指针用于解决数组、字符串中的问题，如二分查找。
1 快慢指针
快慢指针一般都初始化指向链表的头结点，fast指针在前，slow指针灾后。
1.1 判断链表中是否含有环
使用快慢指针判断链表中是否存在环，代码如下
//判断链表中是否有环 bool hasCycle(SinglyListNode* head) { SinglyListNode* fast=head; SinglyListNode* slow=head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) return true; } return false; }
1.2 已知链表中含有环，返回这个环的起始位置
//已知链表中有环 返回这个环的位置 bool detectCycle(SinglyListNode* head) { SinglyListNode* fast = head; SinglyListNode* slow = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; if (slow == fast) break; } slow = head; while (slow != fast) { slow = slow->next; fast = fast->next; } return slow; }
1.3 寻找链表的中点
当链表个数为奇数时中点就是链表中间点，当链表个数为偶数时就是中间位偏右
//判断链表中是否有环 SinglyListNode* geiMedian(SinglyListNode* head) { SinglyListNode* fast = head; SinglyListNode* slow = head; while (fast != NULL && fast->next != NULL) { slow = slow->next; fast = fast->next->next; } return slow; }
1.4寻找链表的倒数第k个元素
首先让快指针先走k步，然后快慢指针同时走，当快指针走到表尾NULL时，慢指针所在的位置就是倒数k个链表节点。
//找链表中倒数k个节点 SinglyListNode* getK(SinglyListNode* head, int k) { SinglyListNode* fast = head; SinglyListNode* slow = head; while (k-- > 0) { fast = fast->next; } while (fast != NULL) { slow = slow->next; fast = fast->next; } return slow; }
2 左右指针
左右指针在数值中实际是分别指向数组的头和尾，将其初始化为 left=0 ， right=nums.size()-1
2.1 二分查找
//二分查找 int binarySearch(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left <= right) { int mid = left - (left - right) / 2; if (nums[mid] == target) return mid; else if (nums[mid] < target) left = mid + 1; else if (nums[mid] > target) right = mid - 1; } return -1; }
2.2 两数之和
注意当数组有序才行
//在数组中找到两数之和等于 target vector<int> twoSum(vector<int>& nums, int target) { int left = 0; int right = nums.size() - 1; while (left < right) { int sum = nums[left] + nums[right]; if (sum == target) return { left,right }; else if (sum < target) left++; else if (sum > target) right--; } return { -1,-1 }; }
2.3 反转数组
void reverse(vector<int>& nums) { int left = 0; int right = nums.size() - 1; while (left < right) { int temp = nums[left]; nums[left] = nums[right]; nums[right] = temp; left++; right--; } }
2.4滑动窗口
本质是维护一个窗口，窗口大小可变，并且不断根据条件滑动，跟新参数。
//滑动窗口框架 void slidingWindow(string s,string t) { unordered_map<char, int>need, window; for (char c : t)need[c]++; int left = 0, right = 0; int valid = 0; while (right < s.size()) { //c是将移入窗口的字符 char c = s[right]; //右移窗口 right++; /* 窗口内数据更新 进行一系列操作 */ cout << "left=" << left << "," << "right=" << right << endl; while ("window need shrink") { char d = s[left]; left++; /* 窗口内数据更新 进行一系列操作 */ } } }
实践题目1：LeetCode76
思路：1、在字符串S中使用左右指针技巧，初始化left=right=0 将索引左闭右开[left, right)称为一个窗口。
2、先不断增加right指针扩大窗口，直到窗口中的字符串符合要求。（包含T中所有字符）
3、停止增加right，转而增加left指针缩小窗口，直到窗口不符合要求（不包含T中所有字符）。同时每增 加left，就要更新结果。
4、重复第2和第3步，直到right到达字符串S的尽头。
string minWindow(string s, string t) { //初始化俩个哈希表 记录窗口内字符和需要字符 unordered_map<char, int> need, window; //将需要字符加入哈希表 for (char c : t)need[c]++; int left = 0, right = 0; //判断窗口内的字符个数 int valid = 0; //记录窗口的开始与结束位置 int start = 0, len = INT_MAX; //右边界开始滑动 while (right < s.size()) { char c = s[right]; right++; //判断当前字符是否在need中，在加入 if (need.count(c)) { window[c]++; if (window[c] == need[c]) valid++; } //当窗口内字符等于need时候开始滑动左边界 while (valid == need.size()) { if (right - left < len) { start = left; len = right - left; } char d = s[left]; left++; //判断当前字符是否在need中，在去除 if (need.count(d)) { if (window[d] == need[d]) valid--; window[d]--; } } } return len == INT_MAX ? "" : s.substr(start, len); }
实战题目2：LeetCode 567
bool checkInclusion(string s1, string s2) { unordered_map<char,int> need,window; for(char c:s1) need[c]++; int left=0,right=0; int valid=0; while(right<s2.size()) { char c=s2[right]; right++; if(need.count(c)) { window[c]++; if(window[c]==need[c]) valid++; } while(right-left>=s1.size()) { if(valid==need.size()) return true; char d=s2[left]; left++; if(need.count(d)) { if(window[d]==need[d]) valid--; window[d]--; } } } return false; }
实战题目3：LeetCode 438
vector<int> findAnagrams(string s, string p) { unordered_map<char,int> need,window; for(char c:p)need[c]++; int left=0,right=0; int valid=0; vector<int> res; while(right<s.size()) { char c=s[right]; right++; if(need.count(c)) { window[c]++; if(window[c]==need[c]) valid++; } while(right-left>=p.size()) { if(valid==need.size()) res.push_back(left); char d=s[left]; left++; if(need.count(d)) { if(window[d]==need[d]) valid--; window[d]--; } } } return res; }
实战题目4：LeetCode 3
int lengthOfLongestSubstring(string s) { unordered_map<char,int>window; int left=0,right=0; int res; while(right<s.size()) { char c=s[right]; right++; window[c]++; while(window[c]>1) { char d=s[left]; left++; window[d]--; } res =max(res,right-left); } return res; }
参考：以上内容来自以下公众号，本文只是做记录，方便自己查看。