双指针、尺取法与滑动窗口

双指针是在数组、字符串或链表上同时维护两个位置，并依据题目的单调性移动它们。指针不回退时，每个元素通常只会被访问常数次，可把许多 O(n²) 枚举优化为 O(n)。

适用条件与常见类型

• 快慢指针：同向、速度不同，适合链表找环和找中点。
• 同向双指针（尺取法/滑动窗口）：维护连续区间 [l, r]，适合可随端点加入、删除而维护状态的问题。
• 对撞指针：从两端向中间移动，需能证明某一端可以被安全舍弃；常见于有序数组、回文和盛水容器。

关键不是“使用两个下标”，而是每次移动都能排除一批不可能的答案。若没有这样的单调性，不能强行套用双指针。

快慢指针：链表环与中点

令慢指针每轮走一步、快指针每轮走两步。无环时快指针会先到达空指针；有环时二者进入环后相对速度为 1，必然相遇。该 Floyd 判环算法的完整步骤是：同时从头结点出发；在 fast 和 fast->next 非空时移动；每轮比较二者是否相等。

bool hasCycle(ListNode* head) {
    ListNode *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}

判环时间 O(n)、额外空间 O(1)。找中点使用同样的移动规则；循环结束时 slow 位于中点。以 fast = head 开始且条件为 fast && fast->next 时，偶数长度链表返回第二个中点。

尺取法与滑动窗口

窗口表示连续区间 [l, r]。基本流程是：右端点扩展并更新状态；在窗口已满足目标（求最短）或违反限制（求最长）时，持续移动左端点并撤销其贡献；在合适时更新答案。两个端点都只向右走，因此总移动次数至多 2n。

例如“和至少为 target 的最短连续子数组”要求数组元素均为正数：右扩时和不减，左缩时和不增，才能保证不漏解。若含负数，这一单调性消失，应考虑前缀和等其他方法。

int minLen(int target, const vector<int>& a) {
    int ans = INT_MAX, sum = 0;
    for (int l = 0, r = 0; r < (int)a.size(); ++r) {
        sum += a[r];                 // 扩展窗口
        while (sum >= target) {      // 当前窗口可行，尝试缩短
            ans = min(ans, r - l + 1);
            sum -= a[l++];
        }
    }
    return ans == INT_MAX ? 0 : ans;
}

上述算法时间 O(n)、额外空间 O(1)。对于“无重复字符的最长子串”等频率约束，可额外维护计数数组或哈希表：右端加入字符，出现重复时从左端删除直至窗口重新合法，再更新最大长度。

对撞指针

有序数组的两数之和从 l = 0、r = n - 1 开始：若 a[l] + a[r] 小于目标，左移会更小而无意义，应令 l++；若大于目标，应令 r--；相等即得到答案。每轮排除一端，时间 O(n)、空间 O(1)。

pair<int, int> twoSumSorted(const vector<int>& a, int target) {
    for (int l = 0, r = (int)a.size() - 1; l < r; ) {
        long long sum = 1LL * a[l] + a[r];
        if (sum == target) return {l, r};
        if (sum < target) ++l;
        else --r;
    }
    return {-1, -1};
}

盛水容器不要求数组有序，但面积由较短板限制。移动较长板只会缩短宽度且限制高度不变，所以每轮移动较短板；三数之和则先排序，固定一个数后在剩余区间使用对撞指针，并跳过相邻重复值，总时间为 O(n²)。