跳转至

# 枚举

本页面将简要介绍枚举算法．

## 简介

枚举（英语：Enumerate）是基于已有知识来猜测答案的一种问题求解策略．

枚举的思想是不断地猜测，从可能的集合中一一尝试，然后再判断题目的条件是否成立．

## 要点

### 给出解空间

建立简洁的数学模型．

枚举的时候要想清楚：可能的情况是什么？要枚举哪些要素？

### 减少枚举的空间

枚举的范围是什么？是所有的内容都需要枚举吗？

在用枚举法解决问题的时候，一定要想清楚这两件事，否则会带来不必要的时间开销．

### 选择合适的枚举顺序

根据题目判断．比如例题中要求的是最大的符合条件的素数，那自然是从大到小枚举比较合适．

## 例题

以下是一个使用枚举解题与优化枚举范围的例子．

例题

给定一个数组，其所有元素互不相同且均不为 0 0．求该数组中和为 0 0 的数对个数．

解题思路

枚举两个数的代码很容易就可以写出来．

C++Python Java

    1
    2
    3
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (a[i] + a[j] == 0) ++ans;

    1
    2
    3
    4
    for i in range(n):
        for j in range(n):
            if a[i] + a[j] == 0:
                ans += 1

    1
    2
    3
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < n; ++j)
        if (a[i] + a[j] == 0) ++ans;

来看看枚举的范围如何优化．由于题中没要求数对是有序的，答案就是有序的情况的两倍（考虑如果 `(a, b)` 是答案，那么 `(b, a)` 也是答案）．对于这种情况，只需统计人为要求有顺序之后的答案，最后再乘上 2 2 就好了．

不妨要求第一个数要出现在靠后的位置．代码如下：

C++Python Java

    1
    2
    3
    4
    for (int i = 0; i < n; ++i)
      for (int j = 0; j < i; ++j)
        if (a[i] + a[j] == 0) ++ans;
    ans *= 2;

    1
    2
    3
    4
    5
    for i in range(n):
        for j in range(i):
            if a[i] + a[j] == 0:
                ans += 1
    ans *= 2

    1
    2
    3
    4
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < i; ++j)
            if (a[i] + a[j] == 0) ++ans;
    ans *= 2;

不难发现这里已经减少了 𝑗 j 的枚举范围，减少了这段代码的时间开销．

我们可以在此之上进一步优化．

两个数是否都一定要枚举出来呢？枚举其中一个数之后，题目的条件已经确定了其他的要素（另一个数）的条件，如果能找到一种方法直接判断题目要求的那个数是否存在，就可以省掉枚举后一个数的时间了．较为进阶地，在数据范围允许的情况下，我们可以使用桶1记录遍历过的数．

C++Python Java

     1
     2
     3
     4
     5
     6
     7
     8
     9
    10
    11
    12
    13
    #include <cstring>
    constexpr int MAXN = 100000;  // 此处 MAXN 是数组内元素的界

    int solve(int n, int a[]) {
      bool met[MAXN * 2 + 1];  // 创建一个能装下 [-MAXN, MAXN] 的桶
      memset(met, 0, sizeof(met));
      int ans = 0;
      for (int i = 0; i < n; ++i) {
        if (met[MAXN - a[i]]) ++ans;  // 如果桶内有想要的元素，答案加一
        met[MAXN + a[i]] = true;  // 无论如何，都要把当前元素放进桶里
      }
      return ans * 2;
    }

    1
    2
    3
    4
    5
    6
    met = [False] * (MAXN * 2 + 1)
    for i in range(n):
        if met[MAXN - a[i]]:
            ans += 1
        met[a[i] + MAXN] = True
    ans *= 2

    1
    2
    3
    4
    5
    6
    boolean[] met = new boolean[MAXN * 2 + 1];
    for (int i = 0; i < n; ++i) {
        if (met[MAXN - a[i]]) ++ans;
        met[MAXN + a[i]] = true;
    }
    ans *= 2;

### 复杂度分析

- 时间复杂度分析：对 𝑎 a 数组遍历了一遍就能完成题目要求，当 𝑛 n 足够大的时候时间复杂度为 𝑂(𝑛)O(n)．
- 空间复杂度分析：𝑂(𝑛 +m a x{|𝑥| :𝑥 ∈𝑎})O(n+max{|x|:x∈a})．

## 习题

- 2811: 熄灯问题 - OpenJudge

## 脚注

1. 桶排序 以及 主元素问题 以及 Stack Overflow 上对桶数据结构的讲解（英文） ↩

> 本页面最近更新：2026/1/7 08:56:54，更新历史
> 发现错误？想一起完善？ 在 GitHub 上编辑此页！
> 本页面贡献者：Tiphereth-A, Ir1d, frank-xjh, NachtgeistW, Xeonacid, Enter-tainer, HeRaNO, ksyx, shuzhouliu, c-forrest, CamberLoid, CCXXXI, Early0v0, Great-designer, heshuyue, hoseahsu, iamtwz, LeiJinpeng, Menci, Planet6174, qiqistyle, ryze, Saisyc, ScrapW, shawlleyw, sshwy, TheWash7, tinjyu, TrickEye, TrisolarisHD, xyf007
> 本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用