数据结构和算法：双指针技巧

双指针技巧，常用于数组和链表此类数据结构中，通过前后指针和快慢指针在单次遍历或少次遍历中求解问题

数组

数组可以双向操作，双指针可前后遍历或同向遍历

167.两数之和Ⅱ-输入有序数组 easy：

给定一个已按照 非递减顺序排列 的整数数组 numbers ，请你从数组中找出两个数满足相加之和等于目标数 target 。

函数应该以长度为 2 的整数数组的形式返回这两个数的下标值。numbers 的下标 从 1 开始计数 。

• 使用双指针，分别从数组头尾遍历，若和小于目标值，则左指针右移，若大于目标值，则右指针左移。

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

209.长度最小的子数组medium：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组，并返回其长度。如果不存在符合条件的子数组，返回 0 。

• 滑动窗口：定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和

  初始状态下，start 和 end 都指向下标 0 ，sum 的值为 0。

  每一轮迭代，将 nums[end] 加到 sum，如果 sum ≥ s，则更新子数组的最小长度，然后将 nums[start] 从 sum 中减去并将 start 右移，直到 sum < s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end 右移。

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

链表

这里提到的链表都为单链表，因此常用同向的快慢指针

141.环形链表 easy: 给定一个链表，判断链表中是否有环，如果链表中存在环，则返回 true 。 否则，返回 false

• .快慢指针：涉及「Floyd 判圈算法」（又称龟兔赛跑算法）

  ​ 定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if(head==nullptr || head->next==nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while(slow!=fast) {
            if(fast==nullptr || fast->next == nullptr) {
                return false;
            }
            fast=fast->next->next;
            slow=slow->next;
        }
        return true;
    }
};

142.环形链表Ⅱ medium：给定一个链表，返回链表开始入环的第一个节点。 如果链表无环，则返回 null

• 快慢指针：定义两个指针fast和slow，slow 指向链表头部 head，fast 每轮走 2 步，slow 每轮走 1 步，fast指针走过链表末端，说明链表无环；

  当fast == slow时， 两指针在环中第一次相遇，设环长为b, 去掉环链长为a, 根据：

  ​ f = 2s （快指针每次2步，路程刚好2倍）

  ​ f = s + nb (相遇时，刚好多走了n圈）

  推出：s = nb

  从head结点走到入环点需要走 ： a + nb， 而slow已经走了nb，那么slow再走a步就是入环点了。

  如何知道slow刚好走了a步, 可以让一指针从head开始，和slow指针一起走，则相遇时刚好就是a步。

/**
 * 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* fast = head;
        ListNode* slow = head;
        while(!(fast == nullptr || fast->next == nullptr)){
            fast = fast->next->next;
            slow = slow->next;
            if(fast==slow){
                fast = head;
                while(fast!=slow){
                    fast=fast->next;
                    slow=slow->next;
                }
                return slow;
            }
        }
        return nullptr;
    }
};

160.相交链表 easy: 给你两个单链表的头节点 headA和headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点，返回 null

• 双指针：无论两链表是否相交，只需要将链表LA和链表LB的链尾对齐，然后从后向前依次比较节点是否相同即可。
  1.从后向前访问的第一节点既不是公共节点则两链表不相交。
  2.从后向前访问的公共节点中最后访问的公共节点则为两链表相交的第一个节点

  因为单链表无法向前遍历节点，但是可以将LA+LB和LB+LA的两条轨道拼接起来，此时尾部对齐，从前往后遍历就能找到公共节点

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(headA==nullptr || headB==nullptr){
            return nullptr;
        }
        ListNode* pA = headA;
        ListNode* pB = headB;
        while(pA != pB) {
            pA = pA == nullptr ? headB : pA->next;
            pB = pB == nullptr ? headA : pB->next;
        }
        return pA;
    }
};