双指针、滑动窗口、前缀和、哈希计数和单调结构不是互相孤立的模板。它们都在利用问题中的某种结构，避免反复计算同一段数据。

本篇重点不是背代码，而是建立选择顺序：题目要求处理连续区间时，先判断窗口能否增量维护；数组已经有序时，考虑相向双指针；需要大量区间和查询时，先做前缀预处理；窗口条件依赖元素种类时，用哈希表维护计数。

一、模式选择表

题目特征 优先考虑 核心状态
有序数组中寻找一对元素 相向双指针 left、right 及当前和
原地删除或压缩数组 同向双指针 读指针与写指针
固定长度连续区间 固定滑动窗口 当前窗口的和、计数或最值
最长/最短合法连续区间 可变滑动窗口 左右边界和维持合法性的状态
多次查询静态区间和 前缀和 prefix[i] 表示前 i 个元素之和
统计窗口内的值或种类 哈希计数 值到出现次数的映射
查找下一个更大/更小元素 单调栈 尚未找到答案的下标
维护滑动窗口最大/最小值 单调队列 候选下标的单调双端队列

滑动窗口通常要求：右端加入元素、左端移除元素后，窗口状态能够高效更新。如果每次移动边界都必须重新扫描整个窗口，就还没有真正把复杂度降下来。

二、相向双指针

给定升序数组，寻找和等于目标值的两个元素下标：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <utility>
#include <vector>

std::pair<int, int> findPairWithSum(
    const std::vector<int>& values,
    long long target
) {
    int left = 0;
    int right = static_cast<int>(values.size()) - 1;

    while (left < right) {
        const long long sum = static_cast<long long>(values[left]) + values[right];
        if (sum == target) {
            return {left, right};
        }
        if (sum < target) {
            ++left;
        } else {
            --right;
        }
    }
    return {-1, -1};
}

移动依据来自数组有序性：

  • 当前和太小，固定右端并把左端右移，才能让和变大；
  • 当前和太大，固定左端并把右端左移，才能让和变小；
  • 被排除的一端不可能再和当前另一端组成答案。

时间复杂度为 O(n)，额外空间为 O(1)。如果输入无序但允许改变顺序，可以先排序到 O(n log n)；如果必须返回原下标，哈希表通常更直接。

三、同向双指针

同向双指针常用于原地压缩。下面将有序数组中的重复值压缩为只保留一次，并返回新长度：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <vector>

int removeDuplicates(std::vector<int>& values) {
    if (values.empty()) {
        return 0;
    }

    int write = 1;
    for (int read = 1; read < static_cast<int>(values.size()); ++read) {
        if (values[read] != values[write - 1]) {
            values[write] = values[read];
            ++write;
        }
    }
    return write;
}

循环中始终保持不变量：[0, write) 已经是去重后的合法结果，read 指向下一个待处理元素。函数只保证前 write 个元素有效，并没有缩小容器；如果题目需要实际删除尾部，可以再调用 values.resize(write)。

四、固定长度滑动窗口

给定数组和窗口长度 k，求所有长度为 k 的连续区间中的最大和：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#include <stdexcept>
#include <vector>

long long maximumWindowSum(const std::vector<int>& values, int k) {
    if (k <= 0 || k > static_cast<int>(values.size())) {
        throw std::invalid_argument("invalid window length");
    }

    long long current = 0;
    for (int i = 0; i < k; ++i) {
        current += values[i];
    }

    long long answer = current;
    for (int right = k; right < static_cast<int>(values.size()); ++right) {
        current += values[right];
        current -= values[right - k];
        if (current > answer) {
            answer = current;
        }
    }
    return answer;
}

每次右移只加入一个元素并移除一个元素，时间复杂度从枚举后重新求和的 O(nk) 降为 O(n)，额外空间为 O(1)。

五、可变滑动窗口

可变窗口通常遵循以下结构：

1
2
3
4
5
6
7
8
9
10
11
int left = 0;
for (int right = 0; right < n; ++right) {
    add(values[right]);

    while (windowIsInvalid()) {
        remove(values[left]);
        ++left;
    }

    updateAnswer(left, right);
}

关键不在循环外形，而在两个问题：

  1. 加入和移除一个元素时，如何在 O(1) 或均摊 O(1) 时间内更新状态；
  2. 窗口失效后，左边界右移是否能单调地恢复合法性。

对于包含负数的“区间和不超过上限”等条件，右移左边界未必让区间和单调减小，普通滑动窗口可能不适用。

六、贯穿场景：最长无重复字节子串

输入一行 ASCII 文本，求最长的不含重复字节的连续子串。使用长度为 256 的数组记录每个字节上次出现的位置。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
// verify: cpp17
#include <array>
#include <cstddef>
#include <iostream>
#include <string>

struct WindowResult {
    std::size_t start;
    std::size_t length;
};

WindowResult longestUniqueWindow(const std::string& text) {
    constexpr std::size_t notSeen = std::string::npos;
    std::array<std::size_t, 256> lastPosition{};
    lastPosition.fill(notSeen);

    std::size_t left = 0;
    WindowResult best{0, 0};

    for (std::size_t right = 0; right < text.size(); ++right) {
        const unsigned char byte = static_cast<unsigned char>(text[right]);
        const std::size_t previous = lastPosition[byte];

        if (previous != notSeen && previous >= left) {
            left = previous + 1;
        }
        lastPosition[byte] = right;

        const std::size_t length = right - left + 1;
        if (length > best.length) {
            best = WindowResult{left, length};
        }
    }
    return best;
}

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    std::string text;
    std::getline(std::cin, text);

    const WindowResult result = longestUniqueWindow(text);
    std::cout << "length=" << result.length << '\n';
    std::cout << "start=" << result.start << '\n';
    std::cout << "value=" << text.substr(result.start, result.length) << '\n';
    return 0;
}

输入：

1
abcaefbb

输出：

1
2
3
length=5
start=1
value=bcaef

执行过程

  • 读到前三个字节 abc 时，窗口为 [0, 2]；
  • right = 3 再次读到 a，它上次出现在窗口内的下标 0，因此把 left 移到 1；
  • 继续加入 e、f，窗口 bcaef 长度达到 5；
  • 再遇到 b 时，左边界跳到上一个 b 之后。

每个右端位置只处理一次，左边界只向右移动，时间复杂度为 O(n)；固定位置表占用 O(1) 空间。

本题处理的是字节，不是 Unicode 字符。UTF-8 中文字符由多个字节编码；如果题目把“字符”定义为 Unicode 码点，就需要先按明确的编码规则解码，不能直接套用 256 项数组。

七、前缀和

若数组不再修改，但需要多次查询半开区间 [left, right) 的和，可以预处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdexcept>
#include <vector>

class PrefixSum {
public:
    explicit PrefixSum(const std::vector<int>& values)
        : prefix_(values.size() + 1, 0) {
        for (std::size_t i = 0; i < values.size(); ++i) {
            prefix_[i + 1] = prefix_[i] + values[i];
        }
    }

    long long query(std::size_t left, std::size_t right) const {
        if (left > right || right >= prefix_.size()) {
            throw std::out_of_range("invalid range");
        }
        return prefix_[right] - prefix_[left];
    }

private:
    std::vector<long long> prefix_;
};

prefix_[i] 表示前 i 个元素之和，所以 [left, right) 的区间和为 prefix_[right] - prefix_[left]。构造需要 O(n) 时间和空间，每次查询为 O(1)。

如果数组频繁修改，普通前缀和每次更新可能是 O(n)，应根据题目考虑树状数组或线段树；它们不属于本轮冲刺的默认范围。

八、单调栈：下一个更大元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <stack>
#include <vector>

std::vector<int> nextGreaterIndex(const std::vector<int>& values) {
    std::vector<int> answer(values.size(), -1);
    std::stack<int> pending;

    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        while (!pending.empty()
            && values[pending.top()] < values[i]) {
            answer[pending.top()] = i;
            pending.pop();
        }
        pending.push(i);
    }
    return answer;
}

栈中保存尚未找到更大值的下标，并保证对应数值单调不增。每个下标最多入栈和出栈一次，所以时间复杂度为 O(n)，空间复杂度为 O(n)。

题目问的是“严格更大”还是“大于等于”会影响比较符号。重复值是验证单调栈代码时必须覆盖的样例。

九、单调队列：滑动窗口最大值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
#include <deque>
#include <stdexcept>
#include <vector>

std::vector<int> slidingWindowMaximum(
    const std::vector<int>& values,
    int k
) {
    if (k <= 0 || k > static_cast<int>(values.size())) {
        throw std::invalid_argument("invalid window length");
    }

    std::deque<int> candidates;
    std::vector<int> answer;
    answer.reserve(values.size() - static_cast<std::size_t>(k) + 1);

    for (int i = 0; i < static_cast<int>(values.size()); ++i) {
        while (!candidates.empty() && candidates.front() <= i - k) {
            candidates.pop_front();
        }
        while (!candidates.empty()
            && values[candidates.back()] <= values[i]) {
            candidates.pop_back();
        }

        candidates.push_back(i);
        if (i + 1 >= k) {
            answer.push_back(values[candidates.front()]);
        }
    }
    return answer;
}

双端队列保存下标而不是数值，因为既要判断元素是否离开窗口，也要读取对应值。队首始终是当前窗口最大值的下标。每个下标最多进出队列一次，时间复杂度为 O(n)，空间复杂度为 O(k)。

十、链表中的双指针

链表没有随机访问能力，但快慢指针仍然适用：

  • fast 每次走两步、slow 每次走一步：寻找中点或判断环；
  • 先让 fast 领先 k 步，再同步移动：寻找倒数第 k 个节点；
  • 两个链表指针走过各自尾部后切换到另一条链：寻找相交节点。

指针移动前始终检查 nullptr，并明确返回的是节点地址、节点值还是下标。

十一、常见错误

  • 输入无序，却直接使用依赖有序性的相向双指针；
  • 窗口右移后只加入新元素，没有移除左端元素；
  • 在 while 收缩窗口前后更新答案的位置错误；
  • 条件不具备单调性，仍然强行使用普通滑动窗口；
  • 哈希计数降为 0 后没有删除键，导致“不同元素种类数”错误；
  • 前缀和的闭区间与半开区间混用；
  • 单调栈和单调队列只保存数值，无法判断原下标和过期位置；
  • 使用 int 保存窗口和或前缀和；
  • 把 UTF-8 字节当作一个字符处理。

十二、考前速查清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 相向双指针
while (left < right) {
    if (condition) {
        ++left;
    } else {
        --right;
    }
}

// 可变滑动窗口
for (int right = 0; right < n; ++right) {
    add(values[right]);
    while (invalid()) {
        remove(values[left++]);
    }
    updateAnswer(left, right);
}

// 半开区间前缀和
rangeSum = prefix[right] - prefix[left];
  • 先写窗口表示的区间和合法条件；
  • 写清加入、移除元素分别修改哪些状态；
  • 证明左右边界只向一个方向移动；
  • 区间统一采用 [left, right) 或 [left, right]，不要中途切换；
  • 需要最值时考虑单调结构，需要种类数时考虑哈希计数。

十三、C++20 可选补充

C++20 可以使用 unordered_map.contains(key) 和 std::span 简化部分表达，但不会改变双指针和滑动窗口的核心逻辑。考试采用 C++17 时继续使用 find() 和容器引用。

十四、已有专题与延伸练习

练习题：

参考资料