三、双指针（two-point）

一、算法核心思想

双指针是指在遍历对象时，使用两个或多个指针进行遍历及相应的操作。大多用于数组操作，这利用了数组连序性的特点。双指针常用来降低算法的时间复杂度，因为使用两个指针可以避免多层循环。
双指针的三个关键点：

• 指针的起始位置的选取
• 指针的移动方向
• 指针的移动速度
  这三个关键点是双指针算法的核心也是难点!

二、算法模型

（一）对撞指针

对撞指针：左右两个指针，向中间靠拢。

1.704.二分查找

（1）思路

数组有序的前提下用双指针进行二分查找，双指针的作用在于"二分"。首先左右两个指针l r，分别指向数组的首元素和尾元素，判断左右指针中间数组下标mid所对应的数组值与目标值的大小关系，共有如下三种情况：

nums[mid] == target 找到目标值，记录数组下标，结束
nums[mid] > target 中间的值大于目标值，应当在区间 [ l, mid-1 ] 中继续查找
nums[mid] < target 中间值小于目标值，应当在区间 [ mid+1 , r ] 中继续查找

（2）代码

class Solution {
public:int search(vector<int>& nums, int target) {if (target < nums[0] || target > nums[nums.size() - 1]) {return -1;}int left = 0, right = nums.size() - 1;while (left <= right) {int med = left + ((right - left) >> 1);if (nums[med] > target) {right = med - 1;}else if (nums[med] < target) {left  = med + 1;}else {return med;}}
return -1;}
};

（3）复杂度分析

时间复杂度：O(logn)
空间复杂度：O(1)

2.15.三数之和

（1）思路

先将 nums 排序，时间复杂度为 O(NlogN)。

固定 3 个指针中最左（最小）元素的指针 k，双指针 i，j 分设在数组索引 (k,len(nums))两端。

双指针 i , j 交替向中间移动，记录对于每个固定指针 k 的所有满足 nums[k] + nums[i] + nums[j] == 0 的 i,j 组合：

1. 当 nums[k] > 0 时直接break跳出：因为 nums[j] >= nums[i] >= nums[k] > 0，即 3 个元素都大于 0 ，在此固定指针 k 之后不可能再找到结果了。
2. 当 k > 0且nums[k] == nums[k - 1]时即跳过此元素nums[k]：因为已经将 nums[k - 1] 的所有组合加入到结果中，本次双指针搜索只会得到重复组合。
3. i，j 分设在数组索引 (k,len(nums))两端，当i < j时循环计算s = nums[k] + nums[i] + nums[j]，并按照以下规则执行双指针移动：
   当s < 0时，i += 1并跳过所有重复的nums[i]；
   当s > 0时，j -= 1并跳过所有重复的nums[j]；
   当s == 0时，记录组合[k, i, j]至res，执行i += 1和j -= 1并跳过所有重复的nums[i]和nums[j]，防止记录到重复组合；

（2）代码

class Solution {
public:vector<vector<int>> threeSum(vector<int>& nums) {// 犹豫不决先排序，步步逼近双指针sort(nums.begin(),nums.end());vector<vector<int>> res;for (int k = 0; k < nums.size() - 2; k ++) {if (nums[k] > 0) break;if (k > 0 && nums[k] == nums[ k - 1]) continue;int i = k + 1,j = nums.size() - 1;while (i < j) {int sum = nums[k] + nums[i] + nums[j];if(sum < 0){while(i < j && nums[i] == nums[++i]);} else if (sum > 0) {while(i < j && nums[j] == nums[--j]);}else {res.push_back(vector<int>{nums[k], nums[i], nums[j]});while(i < j && nums[i] == nums[++i]);while(i < j && nums[j] == nums[--j]);} }}return res;}
};

（3）复杂度分析

时间复杂度：O(N2)
空间复杂度：O(1)

3.167.两数之和-输入有序数组

（1）思路

1. 初始化： 双指针 i , j分别指向数组 numbers的左右两端 （俗称对撞双指针）。
2. 循环搜索： 当双指针相遇时跳出。
3. 计算和 s=numbers[i]+numbers[j]
   若 s>targets，则指针j向左移动，即执行 j=j−1 。
   若 s<targets ，则指针i向右移动，即执行 i=i+1 。
   若 s=targets ，由于题目要求索引从1开始，因此返回数组 [i+1,j+1]。
   

（2）代码

class Solution {
public:vector<int> twoSum(vector<int>& numbers, int target) {if (numbers.size() == 0) {return {0,0};}int slow = 0,fast = numbers.size() - 1;while (slow < fast) {int sum = numbers[slow] + numbers[fast];if (sum < target) slow ++;else if (sum > target) fast--;else return {slow + 1,fast + 1};}return {};}
};

（3）复杂度分析

时间复杂度：O(N) N 为数组 numbers 的长度；双指针共同线性遍历整个数组。
空间复杂度：O(1)

（二）快慢指针

快慢指针：左右两个指针，一块一慢

1.392.判断子序列

（1）思路

（2）代码

class Solution {
public:bool isSubsequence(string s, string t) {int n = s.length();int m = t.length();if (s.size() == 0) return true;if (n > m) return false;int i = 0,j = 0;while (i < n && j < m) {if (s[i] == t[j]) i ++;j ++;}return i == n;}
};

（3）复杂度分析

时间复杂度：O(n+m)
空间复杂度：O(1)

2.876.链表的中心节点

（1）思路

考虑借助快慢双指针 fast, slow ，「快指针 fast」每轮走 2 步，「慢指针 slow」每轮走 1 步。
fast 的步数恒为 slow 的 2 倍，因此当快指针遍历完链表时，慢指针就指向链表中间节点。而由于长度为偶数的链表有两个中间节点，因此需要分两种情况考虑：
链表长度为奇数： 当 fast 走到链表「尾节点」时，slow 正好走到「中间节点」。
链表长度为偶数： 当 fast 走到「null」时（越过「尾节点」后），slow 正好走到「第二个中间节点」。
总结以上规律，应在当 fast 遇到或越过尾节点 时跳出循环，并返回 slow 即可。

（2）代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* middleNode(ListNode* head) {if (head == nullptr || head -> next == nullptr)return head;ListNode* slow = head;ListNode* fast = head;while (fast && fast -> next) {fast = fast -> next -> next;slow = slow -> next;}return slow;}
};

（3）复杂度分析

时间复杂度：O(N)
空间复杂度：O(1)

3.83.删除链表的重复元素

（1）思路

由于给定的链表是排好序的，因此重复的元素在链表中出现的位置是连续的，因此我们只需要对链表进行一次遍历，就可以删除重复的元素。

具体地，我们从指针 cur指向链表的头节点，随后开始对链表进行遍历。如果当前 cur与 cur.next对应的元素相同，那么我们就将 cur.next链表中移除；否则说明链表中已经不存在其它与cur对应的元素相同的节点，因此可以将 cur 指向 cur.next。

注意：当我们遍历到链表的最后一个节点时，cur.next 为空节点，如果不加以判断，访问 cur.next对应的元素会产生运行错误。因此我们只需要遍历到链表的最后一个节点，而不需要遍历完整个链表。

（2）代码

/*** Definition for singly-linked list.* struct ListNode {*     int val;*     ListNode *next;*     ListNode() : val(0), next(nullptr) {}*     ListNode(int x) : val(x), next(nullptr) {}*     ListNode(int x, ListNode *next) : val(x), next(next) {}* };*/
class Solution {
public:ListNode* deleteDuplicates(ListNode* head) {if (head == nullptr) return head;ListNode* cur = head;while (cur -> next) {if (cur -> val == cur -> next -> val) {cur->next = cur->next->next;}else {cur = cur -> next;}}return head;}
};

（3）复杂度分析

时间复杂度：O(n)，n为链表的长度。
空间复杂度：O(1)

4.283.移动0

（1）思路

/注意到以下性质：
//左指针左边均为非零数；
//右指针左边直到左指针处均为零。
//因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。

（2）代码

class Solution {
public:void moveZeroes(vector<int>& nums) {
//注意到以下性质：
//左指针左边均为非零数；
//右指针左边直到左指针处均为零。
//因此每次交换，都是将左指针的零与右指针的非零数交换，且非零数的相对顺序并未改变。int n = nums.size(), left = 0, right = 0;while (right < n) {if (nums[right]) {swap(nums[left++], nums[right]);}right++;}}
};

（3）复杂度分析

时间复杂度：O(n)，其中 n 为序列长度。每个位置至多被遍历两次。
空间复杂度：O(1)，只需要常数的空间存放若干变量。

5.5.最长回文子串

（1）思路

找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧。

如果回文串的长度为奇数，则它有一个中心字符；如果回文串的长度为偶数，则可以认为它有两个中心字符。

（2）代码

class Solution {
public:
//找回文串的难点在于，回文串的的长度可能是奇数也可能是偶数，解决该问题的核心是从中心向两端扩散的双指针技巧。string process(string s,int l,int r) {while (l >= 0 && r < s.size() && s[l] == s[r]) {l --;r ++;}   return s.substr(l + 1,r - l - 1);}string longestPalindrome(string s) {string res = "";for (int i = 0; i < s.length(); i ++) {string s1 = process(s,i,i); // 找到以 s[i] 为中心的回文串string s2 = process(s,i,i + 1);res = res.length() > s1.length() ? res : s1;res = res.length() > s2.length() ? res : s2;}return res;}
};

（3）复杂度分析

（三）滑动窗口