双指针与滑动窗口

三种双指针模式

模式	特点	典型场景
快慢指针	同向，速度不同	链表环检测、去重
左右指针	从两端向中间	有序数组两数之和、反转
滑动窗口	窗口边界单向移动	子串/子数组问题

快慢指针

// 链表是否有环（Floyd 判圈）
bool hasCycle(ListNode *head) {
    auto *slow = head, *fast = head;
    while (fast && fast->next) {
        slow = slow->next;
        fast = fast->next->next;
        if (slow == fast) return true;
    }
    return false;
}
// 如果有环，慢指针入环前走 a 步，环长 b
// 相遇时慢指针走了 a + x，快指针 a + x + nb
// → a + x = nb → 慢指针再走 a 步到环入口

// 有序数组去重 in-place
int removeDuplicates(vector<int> &nums) {
    if (nums.empty()) return 0;
    int slow = 0;
    for (int fast = 1; fast < nums.size(); ++fast)
        if (nums[fast] != nums[slow])
            nums[++slow] = nums[fast];
    return slow + 1;
}

左右指针

// 有序数组两数之和
vector<int> twoSum(const vector<int> &nums, int target) {
    int l = 0, r = nums.size() - 1;
    while (l < r) {
        int sum = nums[l] + nums[r];
        if (sum == target) return {l, r};
        else if (sum < target) ++l;
        else --r;
    }
    return {};
}
// 时间 O(n)

// 反转数组 [l, r] 区间
void reverseRange(vector<int> &nums, int l, int r) {
    while (l < r) swap(nums[l++], nums[r--]);
}

// 盛最多水的容器
int maxArea(const vector<int> &height) {
    int l = 0, r = height.size() - 1, ans = 0;
    while (l < r) {
        ans = max(ans, min(height[l], height[r]) * (r - l));
        height[l] < height[r] ? ++l : --r;  // 矮的移动
    }
    return ans;
}

滑动窗口模板

// 变长窗口 — 找满足条件的最短/最长子数组
int slidingWindow(const vector<int> &nums, int target) {
    int l = 0, sum = 0, ans = INT_MAX;
    for (int r = 0; r < nums.size(); ++r) {
        sum += nums[r];                        // 扩展右边界
        while (sum >= target) {                // 收缩左边界
            ans = min(ans, r - l + 1);
            sum -= nums[l++];
        }
    }
    return ans == INT_MAX ? 0 : ans;
}
// 时间 O(n)：每个元素最多被加入和移除各一次

定长窗口

// 长度为 k 的最大平均值子数组
double maxAvgSubarray(const vector<int> &nums, int k) {
    double sum = accumulate(nums.begin(), nums.begin() + k, 0.0);
    double ans = sum;
    for (int i = k; i < nums.size(); ++i) {
        sum += nums[i] - nums[i - k];    // 滑入 + 滑出
        ans = max(ans, sum);
    }
    return ans / k;
}

经典题——无重复字符最长子串

int lengthOfLongestSubstring(const string &s) {
    vector<int> last(256, -1);  // 字符最后出现位置
    int l = 0, ans = 0;
    for (int r = 0; r < s.size(); ++r) {
        l = max(l, last[s[r]] + 1);    // 有重复 → 跳转左边界
        ans = max(ans, r - l + 1);
        last[s[r]] = r;
    }
    return ans;
}

经典题——最小覆盖子串

string minWindow(const string &s, const string &t) {
    vector<int> need(128, 0), have(128, 0);
    for (char c : t) need[c]++;
    int missing = t.size(), l = 0, start = 0, len = INT_MAX;

    for (int r = 0; r < s.size(); ++r) {
        if (have[s[r]]++ < need[s[r]]) missing--;
        while (missing == 0) {                     // 全覆盖了
            if (r - l + 1 < len) { start = l; len = r - l + 1; }
            if (--have[s[l]] < need[s[l]]) missing++;
            l++;
        }
    }
    return len == INT_MAX ? "" : s.substr(start, len);
}

复杂度分析

所有滑动窗口问题：时间 O(n)，每个元素进窗口一次出窗口一次。空间 O(k)，k 为字符集大小。