枚举-未完纪

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

简介

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

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

要点

给出解空间

建立简洁的数学模型．

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

减少枚举的空间

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

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

选择合适的枚举顺序

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

例题

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

例题

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

解题思路

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

示例前提：下面均使用互不相同、非零的整数；桶版本还要求每个元素在 [-MAXN, MAXN] 内。片段外围须提供数组 a、长度 n 及初始化为 0 的 ans；Python 和 Java 还需定义 MAXN。一般输入范围下还要避免固定宽度整数相加溢出。

C++

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

Python

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

Java

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

来看看枚举的范围如何优化．若 (a_i,a_j) 满足条件，则 (a_j,a_i) 也满足条件；又因为元素均不为 0，满足条件时必有 i≠j．因此可以只枚举 j<i，使每个无序配对只统计一次，再将结果乘 2，得到有序数对个数．代码如下：

C++

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

Python

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

Java

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

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

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

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

C++

#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;
}

Python

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

Java

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)．
空间复杂度分析：O(n+max{|x|:x∈a})．

复杂度校注：上面的固定大小桶在使用前还要初始化；对这份实现，更精确的时间复杂度是 O(n + MAXN)，额外空间是 O(MAXN)，若计入输入数组则为 O(n + MAXN)。把桶大小视为固定常数，或令它与数据规模同阶时，才可进一步按原文讨论写成线性时间。布尔桶依赖题目的“元素互不相同”条件，不能直接推广到含重复值的计数题。