三、双指针（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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

（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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

（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 若 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 {};
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

（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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

（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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

（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++;
        }
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

（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;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

（3）复杂度分析

（三）滑动窗口