文章目录

• 3.1 算法解释
• 3.2 Two Sum
• • 167. 两数之和 II - 输入有序数组（中等）
• 3.3 归并两个有序数组
• • 88. 合并两个有序数组（简单）
• 3.4 快慢指针
• • 142. 环形链表 II
• 3.5 滑动窗口
• • 76. 最小覆盖子串
• 3.6 练习
• • 633. 平方数之和
  • 680. 验证回文串 II
  • 524. 通过删除字母匹配到字典里最长单词
• 3.7 总结

3.1 算法解释

• 双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。

• 若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口(两个指针包围的区域即为当前的窗口)，经常用于区间搜索。

• 若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是排好序的。

• 对于 C++ 语言，指针还可以玩出很多新的花样。一些常见的关于指针的操作如下。

  
  
  

3.2 Two Sum

167. 两数之和 II - 输入有序数组（中等）

1. 题解

   • 因为数组已经排好序了，我们可以采用方向相反的双指针来寻找这两个数字。一个初始指向最小的元素，即数组最左边，向右遍历；另一个指向最大的元素，向左遍历。
   • 如果两个指针指向元素的和等于给定值，那么它们就是答案。如果和小于给定值，我们移动左边的指针，使得当前的和增加一点；如果和大于给定的值，我们移动右边的指针，使得当前的和减少一点。
   • 可以证明，对于排序好的数组，双指针一定能够遍历到最优解：假设最优解的两个数的位置分别是 l 和 r。我们假设左指针还在 l 的左边的时候，右指针已经移动到 r ，此时和小于给定值，左指针会一直向右移动直到来到 l ；同理，假设右指针还在 r 的右边，左指针已经移动到 l ，此时和大于给定值，右指针会一直向左移动直到来到 r 。所以双指针不可能处于 （l，r）之间，又因为不满足条件时指针必须移动一个，所以最终一定会收敛在 l 和 r 。

2. 代码

   class Solution {
   public:vector twoSum(vector& numbers, int target) {int n = numbers.size();int p = 0, q = n - 1;while(numbers[p] + numbers[q] != target){if(numbers[p] + numbers[q] < target)    ++ p; else -- q;}return vector{p + 1, q + 1};}
   };
   

3. 收获

   • 我一开始的做法：将第一个指针指向最小的元素，第二个指针指向它的下一个位置，这样子时间复杂度太高了，后面的点过不去。
   • 学习到：如果最终返回数组，可以直接在 return 里面定义：return vector{p + 1, q + 1};

3.3 归并两个有序数组

88. 合并两个有序数组（简单）

1. 题解

   • 因为两个数组已经排好序了，我们可以把两个指针放到两个数组的末尾，即 nums1 的 m-1 位和 nums2 的 n-1 位。每次将较大的数字复制到 nums1 的末尾，然后向前移动一位。因此我们也需要定位 nums1 的末尾，用到了第三个指针 end。
   • 我们直接利用 m 和 n 当作两个数组的指针，再额外创建一个 end 指针，起始位置为 m+n-1 。每次向前移动 m 或 n 的时候，也要向前移动 end 。这里需要注意，如果 nums1 的数字已经复制完，还需要继续复制 nums2 的数字； 如果 nums2 的数字已经复制完，剩余 nums1 的数字不需要移动，因为他们已经排好序了。

2. 代码

   class Solution {
   public:void merge(vector& nums1, int m, vector& nums2, int n) {int end = m-- + n-- - 1;while(m>=0 && n>=0){nums1[end--] = nums1[m] >= nums2[n] ? nums1[m--] : nums2[n--];}while(n>=0){nums1[end--] = nums2[n--];}}
   };
   

3. 收获

   • 我一开始是定义了两个指针 p 和 q，都是从前往后遍历，但是这样很难处理，每插入一个数字，剩余的数字就需要往后移动一位。而题解的方法灵活很多，思路清晰。

3.4 快慢指针

142. 环形链表 II

1. 题解

   • 对于链表找环路的问题，有一个通用的解法 —— 快慢指针（Floyd判圈法）。Floyd判断法及证明
   • 给定两个指针，分别命名为 fast 和 slow，起始位置在链表的开头。
   • 每次 fast 前进两步， slow 前进一步。 如果 fast 可以走到尽头，说明不存在环路； 如果 fast 可以无限走下去，那么说明一定有环路，且一定存在某个时刻使得 slow 和 fast 相遇。
   • 当 fast 和 slow 第一次相遇的时候，我们将 fast 重新移动到链表开头，并且让 slow 和 fast 每次都前进一步。
   • 当 fast 和 slow 第二次相遇的时候，相遇的节点即为环路的开始点 。

2. 代码

   /*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode(int x) : val(x), next(NULL) {}* };*/
   class Solution {
   public:ListNode *detectCycle(ListNode *head) {ListNode *slow = head, *fast = head;do{if(!fast || !fast->next)    return nullptr;slow = slow -> next;fast = fast -> next -> next;}while(fast != slow);// 如果存在环路，寻找环路的起始点fast = head;while(fast != slow){slow = slow -> next;fast = fast -> next;};return fast;}
   };
   

3. 收获

   • 学习了 快慢指针 （floyd判圈法），并对 「第二次相遇的节点即为环路的开始点」进行了证明，详见参考链接；
   • 灵活使用 do{ } while();

3.5 滑动窗口

76. 最小覆盖子串

1. 题解

   • 本题使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在 r 的左边或重合。
   • 首先使用了长度为 128 的数组来映射字符， ch 表示 t 中的字符数量，flag 表示每个字符是否在 t 中存在；
   • 接着遍历字符串 s，如果字符 s[r] 在 t 中存在，那么就使 --ch[s[r]]，并判断此时 ch[s[r]] 是否仍然大于等于 0 ，如果是的话，cnt ++ ，其中 cnt 统计已经包含的字符个数；
   • 当 cnt 和 t 的长度相等时，也就是说此时已经将字符串 t 覆盖，我们可以移动 l 指针，使得范围缩小。
   • 首先保存能够覆盖字符串 t 的情况，包括左边界和当前的范围；
   • 接着移动左边界 ++l，如果当前字符 s[l] 会在 t 中出现，那么说明左边界越界了，会破坏覆盖字符串 t 的条件。
   • 此时已经确定了覆盖子串最小范围的左右边界。
   • 虽然 for 循环里嵌套了一个 while 循环，但是因为while 循环负责移动 l 指针，且 l 指针只会从左到右移动一次，因此总时间复杂度仍然是 n 。

2. 代码

   class Solution {
   public:string minWindow(string s, string t) {vector ch(128, 0);vector flag(128, false);string ans = "";// 统计 t 中的字符个数for(char c : t){ch[c] ++;flag[c] = true;}// cnt保存已经匹配的字符个数int cnt = 0, l = 0, min_l = 0, min_size = s.size() + 1;for(int r = 0; r < s.size(); ++r){if(flag[s[r]]){if(--ch[s[r]] >= 0){cnt ++;}}while(cnt == t.size()){// 此时已经覆盖子串// 向右移动左边界if(r - l + 1 < min_size){// 保存能够覆盖子串的情况min_l = l;min_size = r - l + 1;}// s[l] 字符在子串里，cnt--，条件被破坏，不能向右移动了if(flag[s[l]] && ++ch[s[l]] > 0){-- cnt;}++ l;}}return min_size > s.size() ? "": s.substr(min_l, min_size);}
   };
   

3. 收获

   • 我一开始是把左指针放到 s 的起点， 右指针放到 s 的最右边，然后依次缩小左右边界，但是这样会超时。
   • 在统计字符个数的时候，由于字符串中包含大小写字母，所以我用了四个长度为 26 的哈希表，分别保存 s 和 t 中字符的出现个数，这样子太繁琐了。题解中直接用了长度为 128 的哈希表（z 的 ascii 码 == 122）保存，首先 ++ 来统计 t 中字符出现情况，然后 – 来扣除 s 中字符出现情况。

3.6 练习

633. 平方数之和

1. 题解

   • 设置双指针 left 和 right ，分别指向 0 和 sqrt（c），左边界容易理解，右边界设置为 sqrt（c）能够保证尽可能缩小检查次数。
   • 接着遍历双指针区间范围的数字，如果平方和等于 c ，说明能够找到，返回 true；小于则移动左指针，大于则移动右指针。当左指针来到右指针的右边时，说明所有情况都已经遍历了一遍，循环结束。
   • 双指针正确性的证明可以见例题1 ，或者该题解（双指针正确性证明）也给出了证明。

2. 代码

   class Solution {
   public:bool judgeSquareSum(int c) {long left = 0, right = (long)sqrt(c);while(left <= right){long sum = left * left + right * right;if(sum == c)   return true;if(sum < c)    left ++;else right --; }return false;}
   };
   

3. 收获

   • 这道题和例题 1 差不多，很容易就想到了。不过我看到 c 的范围在 （0，2³¹ - 1）之间，我还以为预先计算 1 ~ 2¹⁶ 的平方项会提高速度，没想到画蛇添足，以后还是直接计算，如果不能通过再离线处理。

680. 验证回文串 II

1. 题解

   • 设置双指针left 和 right ，分别指向字符串的首尾，左指针向右遍历，右指针向左遍历，依次遍历整个字符串判断是否是回文子串，直到两个指针交换左右位置。
   • 如果双指针指向的两个字符相等，那么各自前进；
   • 如果双指针指向的两个字符不相等，首先判断修改次数，如果 cnt == 1，则不可能形成回文子串，返回 false；否则，将修改次数 cnt ++，紧接着考虑两种情况：删掉左指针指向的字符，或者删掉右指针指向的字符。
   • 不管删掉哪个字符，只需要考虑剩下的字符串能否形成回文子串，这里可以递归调用函数 validPalindrome 来实现。对于删掉字符后的回文子串，由于 left 左边的字符串和 right 右边的字符串已经一一对应了，不需要再次判断，因此只需要考虑 s.substr(left, right - left) 和 s.substr(left + 1, right - left) 两个字符串是否能够形成回文子串。

2. 代码

   class Solution {
   public:int  cnt = 0;bool validPalindrome(string s) {int left = 0, right = s.size() - 1;while(left <= right){if(s[left] == s[right]){left ++, right --;}else{cnt ++;if(cnt <= 1){return validPalindrome(s.substr(left, right - left)) || validPalindrome(s.substr(left + 1, right - left));}else return false; }}return true;}
   };
   

3. 收获

   • 回文子串指的是从前往后和从后往前遍历完全相等的字符串。
   • 一开始没想到递归的方法，弄得有些麻烦。

524. 通过删除字母匹配到字典里最长单词

1. 题解

   • 题目要求返回 长度最长 且 字母序最小 的字符串，因此先对字符串数组 dictionary 自定义排序，如果长度一致则按照字母序升序，否则按照长度降序；
   • 接着遍历 dictionary 的所有元素，设置两个指针 p 和 q，分别指向 s 和 dictionary 当前元素 d ，如果指针指向的字母相同，共同前进一步，否则只移动指向 s 的指针 p；
   • 当 其中一个指向字符串的末尾时该字符串遍历结束，判断 q 指针遍历了字符串 d，如果是的话，说明找到了答案字符串，返回该字符串；否则遍历 dictionary 的下一个元素。

2. 代码

   class Solution {
   public:string findLongestWord(string s, vector& dictionary) {// 将 dictionary 各元素按照长度降序排序// 如果长度一致 按照字典序升序sort(dictionary.begin(), dictionary.end(), [](string s1, string s2){if(s1.size() == s2.size())  return s1 < s2; return s1.size() > s2.size();});for(string d : dictionary){int p = 0, q = 0;while(p < s.size() && q < d.size()){if(s[p] == d[q]){++p, ++q;}else ++p;}if(q == d.size()){return d;}}return "";}
   };
   

3. 收获

   • 这道题不难，一开始我还想用 map 映射排序，后来发现很难实现，而且 sort 本身就可以自定义排序了。

3.7 总结

1. 题目类型：

   • 两个指针相向移动，一个放在起点，一个在终点；
   • 两个指针同向移动，要么都在起点，要么都在终点；
   • 快慢指针，快指针每次走 2 步，慢指针每次走 1 步，当二者第一次相遇时，将快指针移动到起点处，然后两个指针每次都走 1 步，第二次相遇的时候它们都会回到起点；
   • 滑动窗口。

2. 练习题 340 是VIP 题，没做；三道练习题都不算难，滑动窗口的题我比较不熟悉。