我的算法书 - 配对问题

一句话算法

配对问题就是固定右端点 j，把所有合法左端点 i < j 按条件快速数出来。

问题模型

给定一个序列，统计满足某种条件的下标对：

(i,j),\quad i<j

最直接的做法是两层循环枚举所有对，复杂度 $O(n^2)$ 。

配对问题的优化思路是：

从左到右枚举右端点 j。
把 j 左边的信息维护在桶、哈希表、窗口或队列里。
对每个 j，直接查出有多少个 i 能和它配对。

通用形式：

\text{answer}=\sum_{j=1}^{n} s(j)

其中 s(j) 表示“以 j 为右端点的合法配对数量”。

核心直觉

任意一对 (i,j) 都有唯一的右端点 j。所以按右端点分类，一定不重不漏。

黑白气球例子：

位置: 1 2 3 4 5 6
颜色: 0 1 1 0 0 1

当枚举到一个黑气球时，它能和左边所有白气球配对；当枚举到一个白气球时，它能和左边所有黑气球配对。

所以只需要维护左边有多少个 0 和多少个 1。

算法步骤

基础模板：

初始化一个维护历史信息的数据结构 state。
从左到右枚举当前位置 j。
先用 state 计算 s(j)，把它加入答案。
再把 a[j] 加入 state，供后面的右端点使用。

查询要在插入当前元素之前

如果先插入当前元素，就可能把 j 自己当成左端点，破坏 i < j。

算法证明

关键不变量： 处理位置 j 前，state 中只包含下标 < j 的元素信息。

初始化时，state 为空，确实没有任何左端点。
处理 j 时，先查询 state，得到的都是 i < j 的配对。
查询后才插入 a[j]，所以 a[j] 只会参与后续右端点的配对。
任意合法配对 (i,j) 会且只会在枚举到右端点 j 时被统计一次。

所以按右端点统计既不会重复，也不会遗漏。

复杂度分析

不同模型取决于 state 的维护方式：

二值桶： $O(n)$ 。
哈希表计数：期望 $O(n)$ 。
余数桶： $O(n + k)$ 。
滑动窗口计数：期望 $O(n)$ 。
单调队列维护窗口最值： $O(n)$ 。

空间复杂度通常是桶或哈希表大小。

代码实现

二值属性不同配对

C++

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

// Count pairs (i, j), i < j, with different binary values.

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

    int n;
    cin >> n;

    long long cnt[2] = {0, 0};
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        ans += cnt[x ^ 1];
        ++cnt[x];
    }

    cout << ans << '\n';
    return 0;
}

Python

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

        # 统计满足 i < j 且 a[i] != a[j] 的数对数量。
# 输入约定：第一行 n，第二行 n 个取值只有 0/1 的数。
# 扫描时 cnt[1] 只累计与当前值相反的左侧元素，天然保证 i < j。
# 答案上界约 n^2/4，Python int 任意精度，不必担心 C++ 的 long long 溢出。
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)

    cnt = [0, 0]
    ans = 0
    for _ in range(n):
        x = next(data)
        ans += cnt[x ^ 1]  # 异或 1 取反：0<->1
        cnt[x] += 1

    print(ans)


if __name__ == "__main__":
    main()

Two Sum 配对计数

C++

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

// Count pairs (i, j), i < j, with a[i] + a[j] == target.

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

    int n;
    long long target;
    cin >> n >> target;

    unordered_map<long long, long long> cnt;
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        auto it = cnt.find(target - x);
        if (it != cnt.end()) ans += it->second;
        ++cnt[x];
    }

    cout << ans << '\n';
    return 0;
}

Python

python

        1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

        # 统计满足 i < j 且 a[i] + a[j] == target 的数对数量。
# 对每个新元素只查 target - x 的历史出现次数，保证 i < j。
# 计数上界约 n^2/2，Python int 任意精度，无 long long 溢出问题。
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    target = next(data)

    cnt: dict[int, int] = {}
    ans = 0
    for _ in range(n):
        x = next(data)
        ans += cnt.get(target - x, 0)
        cnt[x] = cnt.get(x, 0) + 1

    print(ans)


if __name__ == "__main__":
    main()

同余配对计数

C++

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

// Count pairs (i, j), i < j, with (a[i] + a[j]) % mod == 0.

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

    int n, mod;
    cin >> n >> mod;

    vector<long long> cnt(mod, 0);
    long long ans = 0;

    for (int i = 0; i < n; ++i) {
        long long x;
        cin >> x;
        int r = (int)((x % mod + mod) % mod);
        int need = (mod - r) % mod;
        ans += cnt[need];
        ++cnt[r];
    }

    cout << ans << '\n';
    return 0;
}

Python

python

        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

        # 统计满足 i < j 且 (a[i] + a[j]) % mod == 0 的数对数量。
# 对每个新元素只查它的补余数 need，保证 i < j。
# 负数取模在 C++ 里是截断取模，这里用 (x % mod + mod) % mod 统一到 [0, mod)；
# Python 的 % 本身返回非负结果，但仍保留该写法以对齐语义。
# 计数上界约 n^2/2，Python int 任意精度，无 long long 溢出问题。
import sys


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    mod = next(data)

    cnt = [0] * mod
    ans = 0
    for _ in range(n):
        x = next(data)
        r = (x % mod + mod) % mod
        need = (mod - r) % mod  # r == 0 时补余数仍是 0
        ans += cnt[need]
        cnt[r] += 1

    print(ans)


if __name__ == "__main__":
    main()

距离限制相等配对

C++

cpp

        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

        #include <bits/stdc++.h>
using namespace std;

// Count pairs (i, j), i < j, with a[i] == a[j] and j - i <= k.
// The map stores values inside the current left window [j-k, j-1].

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

    int n, k;
    cin >> n >> k;
    vector<long long> a(n);

    unordered_map<long long, long long> cnt;
    long long ans = 0;

    for (int j = 0; j < n; ++j) {
        cin >> a[j];

        if (j > k) {
            long long expired = a[j - k - 1];
            auto it = cnt.find(expired);
            if (it != cnt.end()) {
                --it->second;
                if (it->second == 0) cnt.erase(it);
            }
        }

        auto it = cnt.find(a[j]);
        if (it != cnt.end()) ans += it->second;
        ++cnt[a[j]];
    }

    cout << ans << '\n';
    return 0;
}

Python

python

        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

        # 统计满足 i < j、a[i] == a[j] 且 j - i <= k 的数对数量。
# 不变量：读入 a[j] 前，cnt 里恰好是窗口 [j-k, j-1] 内各值的出现次数。
# 下标从 0 开始；先剔除 a[j-k-1] 再加入 a[j]，保证距离恰好不超过 k。
# 计数上界约 n^2/2，Python int 任意精度，不会像 C++ 的 long long 溢出。
import sys

prev: list[int] = []  # prev[j] 保存已读入的 a[j]，用于窗口过期时按值删除。


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    k = next(data)

    cnt: dict[int, int] = {}
    ans = 0
    for j in range(n):
        x = next(data)

        if j > k:
            expired = prev[j - k - 1]
            cnt[expired] -= 1
            if cnt[expired] == 0:
                del cnt[expired]

        ans += cnt.get(x, 0)
        cnt[x] = cnt.get(x, 0) + 1
        prev.append(x)

    print(ans)


if __name__ == "__main__":
    main()

距离限制最大配对和

C++

cpp

        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 <bits/stdc++.h>
using namespace std;

// Given a[0..n-1], find max a[i] + a[j] with i < j and j - i <= k.
// Monotonic deque keeps candidate i with maximum a[i] in the current window.

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

    int n, k;
    cin >> n >> k;
    vector<long long> a(n);
    for (long long &x : a) cin >> x;

    deque<int> q;
    long long ans = LLONG_MIN;

    for (int j = 0; j < n; ++j) {
        while (!q.empty() && q.front() < j - k) q.pop_front();

        if (!q.empty()) {
            ans = max(ans, a[q.front()] + a[j]);
        }

        while (!q.empty() && a[q.back()] <= a[j]) q.pop_back();
        q.push_back(j);
    }

    cout << ans << '\n';
    return 0;
}

Python

python

        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

        # 求满足 i < j 且 j - i <= k 的 a[i] + a[j] 最大值。
# 单调队列维护当前窗口内 a[i] 递减的下标，队首即窗口最大值。
# 队首过期条件 q[0] < j - k 对应 C++ 的 q.front() < j - k。
# 无合法配对（n < 2）时与 C++ 一致输出 LLONG_MIN，故用哨兵 NEG。
import sys
from collections import deque

NEG = -(1 << 63)  # LLONG_MIN，对齐 C++ 初值语义


def main() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    n = next(data)
    k = next(data)
    a = [next(data) for _ in range(n)]

    q: deque[int] = deque()
    ans = NEG
    for j in range(n):
        while q and q[0] < j - k:
            q.popleft()

        if q:
            ans = max(ans, a[q[0]] + a[j])

        # 队尾元素不可能再作为后续窗口最大值，弹出；保留相等值取更靠右的下标。
        while q and a[q[-1]] <= a[j]:
            q.pop()
        q.append(j)

    print(ans)


if __name__ == "__main__":
    main()

测试用例

黑白气球输入：

6
0 1 1 0 0 1

输出：

Two Sum 输入：

6 10
1 5 3 4 9 7

输出：

距离限制相等配对输入：

6 2
1 2 1 3 1 2

输出：

应用分类详解

配对问题的本质是“右端点枚举 + 左侧信息查询”。

一、属性配对

典型模式： 两个元素的类别满足相同、不同、互补等条件。

识别信号： 黑白、颜色、性别、类别、标签。

核心建模： 用桶记录左侧各类别数量。

应用场景	经典题目	核心思路
黑白气球	本页示例	当前是 0 就加左侧 1 的数量，当前是 1 就加左侧 0 的数量
同色配对	luogu-P1311	统计同色左端点，并处理额外有效性条件

二、数值配对

典型模式： 要求 $a_i+a_j=K$ 、 $a_i-a_j=K$ 或满足某个目标值。

识别信号： “两数之和”“差为 K”“找一对数”。

核心建模： 枚举 a[j]，在哈希表中查需要的另一半。

应用场景	经典题目	核心思路
Two Sum 计数	noiopenjudge ch0201-6184	查 `target - a[j]`
A-B=C 数对	luogu-P1102	固定一个端点，查另一个值出现次数

三、同余配对

典型模式： 两数和能被 k 整除。

识别信号： “整除”“余数”“mod k”。

核心建模： 当前余数为 r，需要左侧余数 (k-r)%k。

应用场景	经典题目	核心思路
和为 k 的倍数	同余配对基础题	用余数桶
分组配对	数论基础题	先按余数分类再计数

四、距离限制配对

典型模式： 配对还要求 j-i <= k。

识别信号： “距离不超过”“最近 k 个”“窗口内”。

核心建模： 只维护 [j-k, j-1] 这个窗口中的历史信息，过期元素要移除。

应用场景	经典题目	核心思路
窗口内同值配对	本页示例	`add/remove/query` 动态维护桶
选择客栈	luogu-P1311	条件有效后，把历史同色数量转为可配对数量

五、窗口最值配对

典型模式： 配对不是计数，而是求窗口内最大/最小值。

识别信号： “距离不超过 k 的最大两数和”“滑动窗口最大值”。

核心建模： 计数桶不适合维护最值，使用单调队列保留窗口内最强候选。

应用场景	经典题目	核心思路
滑动窗口最值	luogu-P1886	单调队列维护窗口最大/最小
距离限制最大配对和	本页模板	对每个 `j`，取窗口内最大 `a[i]`

经典例题

luogu-P1102 A-B 数对：数值配对计数。
luogu-P1311 选择客栈：属性配对叠加区间有效性。
luogu-P1886 滑动窗口：单调队列维护窗口最值。
noiopenjudge ch0201-6184 找和为 K 的两个元素：Two Sum 基础题。