查看“︁09-进阶算法/02-双指针”︁的源代码


== 双指针 ==

双指针用两个指针在数组上移动，将原本 <math>O(n^2)</math> 的枚举优化到 <math>O(n)</math>。

=== 对撞指针 ===

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

<syntaxhighlight lang="cpp">
// 在有序数组 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--;
}
</syntaxhighlight>

=== 快慢指针 ===

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

<syntaxhighlight lang="cpp">
// 判断链表中是否有环
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;
}
</syntaxhighlight>

=== 滑动窗口 ===

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

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

[[Category:进阶算法]]
[[Category:三三文档]]