01 双指针基础

双指针简介

​ **双指针的用途：**双指针主要用于单循环遍历线性表数据结构，两个指针指向不同的元素，从而协同完成任务（通常双指针分别指向元素比较，或者两元素联合与某一条件比较）

​ **双指针的特点：**不管数据输入是字符串、数组还是链表，使用一般方法的遍历方法时间复杂度度在O(n^3)和O(n^2)使用双指针对其进行遍历的平均时间复杂度为O(nlogn)，最好的情况下时间复杂度为O(n)

​ 两种特殊形式的双指针

• 碰撞指针 Opposite directional：两个指针指向同一线性表，但是遍历方向相反，一个指针指向开头，另一个指向末尾，它们相向移动直到相遇或满足其他特殊条件为止
• 快慢指针 Equi-directional：两个指针指向同一线性表，遍历方向相同，且两个指针起点可以相同，也可以不同形成一个滑动窗口，两个指针以不同的策略移动，直到两个指针的值相等或满足其他特殊条件为止

88 合并两个有序数组 (opens new window)

给定两个有序数组，把两个数组合并为一个

输入是两个数组和它们分别的长度 m 和 n。其中第一个数组的长度被延长至 m + n，多出的 n 位被 0 填补。题目要求把第二个数组归并到第一个数组上，不需要开辟额外空间。

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 输出：[1,2,2,3,5,6] 解释：需要合并 [1,2,3] 和 [2,5,6] 。合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

解析：

​ 因为两个数组都是有序的，所以可以把两个指针分别放在两个数组的末尾，即 nums1 的 m-1 位和 nums2 的 n-1 位。每次将较大的那个数字复制到 nums1 的后边，然后向前移动一位。

​ 因为本题是将结果全部存储在 nums1 中，所以还要一个指针指向 nums1 剩余空间的末尾，以便复制。

​ 还需要分析输入的几种特殊情况：

• nums2 为空，不管 nums1 是否为空直接返回 nums1
• nums1 元素为空，直接将 nums2 中元素位置不变的移入 nums1 中即可
• nums1 先于 nums2 遍历完，直接将 nums2 中剩余元素按顺序移入 nums1 中即可

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        # nums2 为空，不管 nums1 是否为空直接返回 nums1
        if(!n){
            return;
        }
        int tail1 = m-1, tail2 = n-1, tail = m+n-1;
        while(tail1>=0 && tail2>=0){
            if(nums1[tail1]>nums2[tail2]){
                nums1[tail--] = nums1[tail1--];
            }else{
                nums1[tail--] = nums2[tail2--];
            }
        }
        # nums1 先于 nums2 遍历完，直接将 nums2 中剩余元素按顺序移入 nums1 中即可
        while(tail2>=0){
            nums1[tail--] = nums2[tail2--];
        }
    }
};

524 通过删除字母匹配到字典里最长单词 (opens new window)

给定一个字符串 s 和一个字符串数组 dictionary ，找出并返回 dictionary 中最长的字符串，该字符串可以通过删除 s 中的某些字符得到。

输入一个字符串和一个字符串数组，输出一个数组中按条件要求的字符串，如果答案不止一个，返回长度最长且字母序最小的字符串。

输入：s = "abpcplea", dictionary = ["ale","apple","monkey","plea"]
输出："apple"

解析：

​ 根据题意，我们需要完成两个任务：首先找到 s 可构成字符串数组中的所有字符串；然后，我们要选出这些候选字符串中长度最长且字母序最小的。

​ 第一个任务我们采用双指针完成，一个指针指向 s 的首元素，从左向右遍历；另一个指针指向字典中当前比较的字符串首元素，也从左向右遍历，每匹配一个元素该指针移动一步。如果全都匹配，形成一个候选字符串。

​ 第二个任务我们可以对字典进行预处理，根据字符串长度进行排序，优先匹配较长的字符串，只要匹配成功就直接返回该字符串。

class Solution {
public:
    string findLongestWord(string s, vector<string>& dictionary) {
        // labmda表达式自定义排序
        sort(dictionary.begin(), dictionary.end(), [](string a, string b){
            // 让字母序更小的排在前面
            if(a.size()==b.size()) return a < b;
            // 让长度更长的排在前面
            return a.size() > b.size();
        });
        
        for(const auto str: dictionary){
            int ps = 0, pstr = 0;
            while(ps<s.size() && pstr<str.size()){
                if(s[ps]==str[pstr]){
                    ++pstr;
                }
                ++ps;
            }
            if(pstr==str.size()){
                return str;
            }
        }
        return "";
    }
};

160 相交链表 (opens new window)

给定两个单链表的头节点 headA 和 headB ，找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null 。 输入两个单链表，输出一个节点表示两链表的交点。

输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3 输出：Intersected at '8' 解释：相交节点的值为 8 （注意，如果两个链表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。

解析：

​ 用双指针可以简单解决本题，我们定义两个指针分别指向两个链表的头节点 pa 和 pb，他们同时出发从左向右遍历，如果遍历完当前链表就接着从另一个链表的头节点开始遍历。这种遍历方式有如下两种情况：

• 如果两个链表存在交点，假设 headA 到交点的节点个数为 a，headB 到交点的节点个数为 b，交点到链表尾节点的节点个数为 c。那么在遍历过程中 pa 的移动距离为 a + c + b，而 pb 的移动距离为 b + c + a，所以 pa 和 pb 最终会在交点处相遇。
• 如果两个链表不存在交点，那么在遍历过程中 pa 的移动距离为 a + b，pb 的移动距离为 b + a，所以 pa 和 pb 最终会在两个链表结尾相等，返回 nullptr

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA == nullptr || headB == nullptr){
            return nullptr;
        }
        ListNode *pa = headA, *pb = headB;
        while(pa!=pb){
            if(pa){
                pa = pa->next;
            }else{
                pa = headB;
            }
            if(pb){
                pb = pb->next;
            }else{
                pb = headA;
            }
        }
        return pa;
    }
};