09-进阶算法/02-双指针

双指针

双指针用两个指针在数组上移动，将原本 [math]\displaystyle{ O(n^2) }[/math] 的枚举优化到 [math]\displaystyle{ O(n) }[/math]。

对撞指针

左右指针向中间移动，常用于有序数组的两数和问题：

// 在有序数组 a 中找两数之和等于 target
int l = 1, r = n;
while (l < r)
{
    int sum = a[l] + a[r];
    if (sum == target) return {l, r};
    else if (sum < target) l++;
    else r--;
}

快慢指针

快指针每次走两步，慢指针每次走一步：

// 判断链表中是否有环
bool has_cycle(Node* head)
{
    Node *slow = head, *fast = head;
    while (fast && fast->next)
    {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

滑动窗口

维护一个区间 [math]\displaystyle{ [l, r] }[/math]，满足条件时右指针右移扩大窗口，不满足时左指针右移缩小窗口：

int l = 1;
for (int r = 1; r <= n; r++)
{
    // 加入 a[r]
    while (/* 窗口不满足条件 */)
    {
        // 移除 a[l]
        l++;
    }
    // 此时 [l, r] 满足条件，更新答案
}