LeetCode解题记录(双指针专题)
1. 算法解释
双指针主要用于遍历数组，两个指针指向不同的元素，从而协同完成任务。也可以延伸到多个数组的多个指针。
若两个指针指向同一数组，遍历方向相同且不会相交，则也称为滑动窗口（两个指针包围的区域即为当前的窗口），经常用于区间搜索。
若两个指针指向同一数组，但是遍历方向相反，则可以用来进行搜索，待搜索的数组往往是排好序的。
对于 C++ 语言，指针还可以玩出很多新的花样。一些常见的关于指针的操作如下。
1.1 指针与常量
1.2 指针函数与函数指针
static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"// addition是指针函数，一个返回类型是指针的函数int* addition(int a, int b) {int* sum = new int(a + b);return sum;}int subtraction(int a, int b) {return a - b;}// 这里第三个参数，接收函数指针int operation(int x, int y, int (*func)(int, int)) {return (*func)(x, y);}int main() {// minus是函数指针，指向函数的指针int (*minus)(int, int) = subtraction;int* m = addition(1, 2);int n = operation(3, *m, minus);cout << "*m: " << *m << " " << "n: " << n << endl;return 0;}
函数指针，需要大家了解
运行结果为
2. 两数之和
167. 两数之和 II – 输入有序数组
给定一个已按照 升序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。
函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 ，所以答案数组应当满足 1 <= answer[0] < answer[1] <= numbers.length 。
你可以假设每个输入只对应唯一的答案，而且你不可以重复使用相同的元素。
示例 1：
输入：numbers = [2,7,11,15], target = 9输出：[1,2]解释：2 与 7 之和等于目标数 9 。因此 index1 = 1, index2 = 2 。
示例 2：
输入：numbers = [2,3,4], target = 6输出：[1,3]
示例 3：
输入：numbers = [-1,0], target = -1输出：[1,2]
提示：
2 <= numbers.length <= 3 * 104-1000 <= numbers[i] <= 1000numbers 按 递增顺序 排列-1000 <= target <= 1000仅存在一个有效答案
题解
因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。
- 如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。
- 如果两个指针指向元素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。
- 如果两个指针指向元素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。
证明
可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最
优解的两个数的位置分别是 l 和 r。我们假设在左指针在 l 左边的时候，右指针已经移动到了 r；
此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达 l。同理，如果我们假设
在右指针在 r 右边的时候，左指针已经移动到了 l；此时两个指针指向值的和大于给定值，因此
右指针会一直左移直到到达 r。所以双指针在任何时候都不可能处于 (l,r) 之间，又因为不满足条
件时指针必须移动一个，所以最终一定会收敛在 l 和 r。
代码
static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"class Solution {public:vector<int> twoSum(vector<int>& numbers, int target) {int l = 0, r = numbers.size() - 1, sum;while (l < r) {sum = numbers[l] + numbers[r];if (sum == target) {break;}if (sum < target) {++l;}else {--r;}}// 这里是因为题目要求下标从1开始return vector<int>{l + 1, r + 1};}};
执行结果
3. 合并两个有序数组
88. 合并两个有序数组
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
初始化 nums1 和 nums2 的元素数量分别为 m 和 n 。你可以假设 nums1 的空间大小等于 m + n，这样它就有足够的空间保存来自 nums2 的元素。
示例 1：
输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3输出：[1,2,2,3,5,6]
示例 2：
输入：nums1 = [1], m = 1, nums2 = [], n = 0输出：[1]
提示：
nums1.length == m + nnums2.length == n0 <= m, n <= 2001 <= m + n <= 200-109 <= nums1[i], nums2[i] <= 109
题解
因为这两个数组已经排好序，我们可以把两个指针分别放在两个数组的末尾，即 nums1 的 m − 1 位和 nums2 的 n − 1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。
因为我们也要定位 nums1 的末尾，所以我们还需要第三个指针，以便复制。
在以下的代码里，我们直接利用 m 和 n 当作两个数组的指针，再额外创立一个 pos 指针，起始位置为 m +n−1。每次向前移动 m 或 n 的时候，也要向前移动 pos。这里需要注意，如果 nums1的数字已经复制完，不要忘记把 nums2 的数字继续复制；如果 nums2 的数字已经复制完，剩余nums1 的数字不需要改变，因为它们已经被排好序。
注意 这里我们使用了
++ 和–的小技巧：a++ 和 ++a 都是将 a 加 1，但是 a++ 返回值为 a，而++a 返回值为 a+1。如果只是希望增加 a 的值，而不需要返回值，则推荐使用 ++a，其运行速度会略快一些。
代码
static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"class Solution {public:void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {// 这里m--返回的是m,但是m实际上已经减小了int pos = m-- + n-- -1;while(m>=0&&n>=0){nums1[pos--] = nums1[m] > nums2[n]?nums1[m--]:nums2[n--];}while(n>=0){nums1[pos--] = nums2[n--];}}};
执行结果
4. 快慢指针
142. 环形链表 II
给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。注意，pos 仅仅是用于标识环的情况，并不会作为参数传递到函数中。
说明：不允许修改给定的链表。
进阶：
你是否可以使用 O(1) 空间解决此题？
示例 1：
输入：head = [3,2,0,-4], pos = 1输出：返回索引为 1 的链表节点解释：链表中有一个环，其尾部连接到第二个节点。
示例 2：
输入：head = [1,2], pos = 0c输出：返回索引为 0 的链表节点解释：链表中有一个环，其尾部连接到第一个节点。
示例 3：
输入：head = [1], pos = -1输出：返回 nullc解释：链表中没有环。
提示：
链表中节点的数目范围在范围 [0, 104] 内-105 <= Node.val <= 105cpos 的值为 -1 或者链表中的一个有效索引
题解
结论
对于链表找环路的问题，有一个通用的解法—─快慢指针(Floyd判圈法）。给定两个指针，分别命名为 slow和 fast，起始位置在链表的开头。每次fast 前进两步，slow前进一步。如果fast可以走到尽头，那么说明没有环路;如果fast 可以无限走下去，那么说明一定有环路，且一定存在一个时刻slow和fast相遇。当slow和 fast第一次相遇时，我们将fast重新移动到链表开头，并让 slow和fast每次都前进一步。当slow和 fast第二次相遇时，相遇的节点即为环路的开始点。
详解
static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"原理：首先初始化快指针 fast = head.next.next 和 slow = head.next，此时快指针走的路长为2, m慢指针走的路长为1，之后令快指针每次走两步，慢指针每次走一步，这样快指针走的路长始终是慢指针走的路长的两倍，若不存在环，直接返回None，若存在环，则 fast 与 slow 肯定会在若干步之后相遇；性质1：设从head需要走 a 步到达环的入口，如果环存在的话，再走 b 步可以再次到达该入口（即环的长度为b），如果存在环的话，上述描述的 快指针 fast 和慢指针slow 必然会相遇，且此时slow走的路长小于 a + b(可以自行证明)，设其为 a + x，当快慢指针相遇时，快指针已经至少走完一圈环了，不妨设相遇时走了完整的m圈(m >= 1)，有：快指针走的路长为 a + mb + x慢指针走的路长为 a + x由于快指针fast 走的路长始终是慢指针的 2倍，所以：a + mb + x = 2(a + x)化简可得：a = mb - x ------------- (*)当快指针与慢指针相遇时，由于 <性质1> 的存在，可以在链表的开头初始化一个新的指针，称其为 detection, 此时 detection 距离环的入口的距离为 a，此时令 detection 和 fast 每次走一步，会发现当各自走了 a 步之后，两个指针同时到达了环的入口，理由分别如下：detection不用说了，走了a步肯定到刚好到入口fast已经走过的距离为 a + mb + x，当再走 a 步之后，fast走过的总距离为 2a + mb + x，带入性质1的(*)式可得：2a + mb + x = a + 2mb，会发现，fast此时刚好走完了整整 2m 圈环，正好处于入口的位置。基于此，我们可以进行循环，直到 detection 和fast 指向同一个对象，此时指向的对象恰好为环的入口。
代码
/*** 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) {// 1.判断是否有环if(head==NULL){return NULL;}// 创建两个快慢指针ListNode* fast = head;ListNode* slow = head;// 进行循环判断while(fast!=NULL && fast->next!=NULL){// fast走两步fast = fast->next->next;// slow走一步slow = slow->next;// 当fast=slow时,证明有环，跳出循环if(fast==slow){break;}}// 将无环的情况返回NULLif(fast==NULL||fast->next==NULL){return NULL;}// 如果有环，则将fast返回到头节点fast = head;while(fast!=slow){// fast与slow都一步一个节点fast = fast->next;slow = slow->next;}// 当fast与slow相遇时，则为入环的第一个节点return fast;}};
还有一种写法
ListNode *detectCycle(ListNode *head) {ListNode *slow = head, *fast = head;// 判断是否存在环路do {if (!fast || !fast->next) return nullptr;fast = fast->next->next;slow = slow->next;} while (fast != slow);// 如果存在，查找环路节点fast = head;while (fast != slow){slow = slow->next;fast = fast->next;}return fast;}
执行结果
5. 平方数之和
633. 平方数之和
思路
两种方法
1）双指针
由于a,b两个数的范围在0到根号C之间，因此，我们用两个指针指向左边和右边
如果
- 平方和大于c，则右边的指针减1
- 平方和小于c，则左边的指针加1
- 平方和等于c，则返回true
代码
class Solution {public:bool judgeSquareSum(int c) {long r = 0, l = (int)sqrt(c), sum;while (r <= l) {sum = r * r + l * l;if (sum == c) {return true;}if (sum < c) {++r;}else {--l;}}return false;}};
执行结果
2）枚举法
简单来说就是先找一个数a，然后另外一个数就是根号下C-a*a，然后把这个数取整，计算平方和，等于c就返回true，否则返回false
下面放上官方的代码，很好理解
class Solution {public:bool judgeSquareSum(int c) {for (long a = 0; a * a <= c; a++) {double b = sqrt(c - a * a);if (b == (int)b) {return true;}}return false;}};
6. 验证回文字符串
680. 验证回文字符串 Ⅱ
题解
题目要求最多删一个字符，所以情况比较简单，我们可以用双指针把删除一个字符后出现的两种情况写出来就好。
双指针分别为head 和 tail。 head从左往右遍历，tail从右往左遍历。
遇到s[head] != s[tail]时，就分化为两种情况即
- head = head + 1, tail = tail
- head = head, tail = tail – 1
- 分别从这两种情况进行判断即可，如果还有不等情况，那么就返回false。
代码
static string Blog_Adress = "https://www.cnblogs.com/wanghongyang/"class Solution {public:bool validPalindrome(string s) {if (s.empty() || s.size() == 1)return true;int length = s.size();int head = 0, tail = length - 1;while (head < tail) //正常双指针判断回文字符串{if (s[head] == s[tail]){++head;--tail;}elsebreak; //从分歧点退出}// 因为如果是正常退出，即head>=tailif (head >= tail) //如果是正常退出return true;//情况1int new_head = head + 1, new_tail = tail;int flag1 = true, flag2 = true;while (new_head < new_tail){if (s[new_head] == s[new_tail]){++new_head;--new_tail;}else{flag1 = false;break;}}//情况2new_head = head;new_tail = tail - 1;while (new_head < new_tail){if (s[new_head] == s[new_tail]){++new_head;--new_tail;}else{flag2 = false;break;}}//由于对两种情况进行遍历，所以只要有一种能满足回文，那就可以！return flag1 || flag2;}};
执行结果
7. 删除字母匹配到字典里最长单词
524. 通过删除字母匹配到字典里最长单词
题解
双指针，但是在使用双指针前需要对被查找集合做排序
1，根据题目要求，先将dictionary的字符串按照字符串的长度从大到小排序，且字符串符合字典序，进行排序，目的是为了接下查找时，dictionary中第一个符合条件字符串的即为题目要求的答案。
2，定义并初始化，字符串s的长度s_len，dictionary的长度d_len，dictionary中字符串的长度ds_len，指向字符串s的指针s_ptr，指向dictionary中第i个字符串的指针ds_ptr。
3，for循环遍历dictionary中所以字符串，获取当前dictionary中第i个的字符串的长度
4，while循环使用双指针，比较字符串s是否包含当前第i个dictionary中的字符串，
如果包含，则d_ptr遍历到dictionary中第i个的字符串的末尾，即d_ptr == ds_len – 1，返回dictionary[i]即为答案，即返回长度最长且字典序最小的字符串。
如果不包含，则d_ptr未遍历到dictionary中第i个的字符串的末尾，且s_ptr遍历到字符串s的末尾
5，退出当前while循环，即将遍历dictionary中的第i+1个字符串，双指针归零为下一个while循环做准备
6，如果退出for循环，则表示答案不存在，则返回空字符串。
代码
class Solution {public:string findLongestWord(string s, vector<string>& dictionary) {//字符串的长度从大到小排序，且字符串符合字典序auto cmp = [&](string& a, string& b){if (a.size() == b.size()) {return a < b;}return a.size() > b.size();};sort(dictionary.begin(), dictionary.end(), cmp);int s_len = s.size(), d_len = dictionary.size(), ds_len = 0;int s_ptr = 0, d_ptr = 0;//双指针方法，遍历字典for (int i = 0; i < d_len; ++i){ds_len = dictionary[i].size(); //当前字典的字符串的长度while (s_ptr < s_len && d_ptr < ds_len){if (s[s_ptr] == dictionary[i][d_ptr]) //存在相等的字母{if (d_ptr == ds_len - 1) //且已经到达当前字符串的末尾，即存在，因为已经排序，所以第一个符合条件的即为答案{return dictionary[i];}//当前字典的字符串的下一个字母++d_ptr;}//匹配被查找字符串的下一个字母++s_ptr;}//比较字典的下一个字符串，被查找字符串的s_ptr归零s_ptr = 0;//进行字典的下一个字符串比较，d_ptr归零d_ptr = 0;}return "";}};
运行结果
8. 总结
这个系列让我了解到双指针的一些题目场景，了解了双指针的使用，然后双指针的部分就到这里，下期开始写二分查找