AcWing 3404谁是你的潜在朋友：桶计数入门题解

1. 先读懂题意：AcWing 3404 谁是你的潜在朋友到底在问什么

最近刷到了AcWing 3404这道题，题目叫“谁是你的潜在朋友”。第一眼看到这个名字，我还以为要建图、求连通块，读完题才发现完全不是那么回事。它是一道非常典型的桶计数入门题，核心考点只有一句话：能不能想到用书编号做下标，一次性统计出每本书被多少人喜欢。题目描述不复杂：现有N个人，编号1到N；有M本书，编号1到M。每个人报出自己最喜欢的一本书的编号，所谓“潜在朋友”，就是和你喜欢同一本书的其他所有人。要求输出每个人的潜在朋友个数，如果没有潜在朋友，则输出BeiJu。

这道题在算法难度上属于入门级别，但非常适合练手。它能帮刚接触算法竞赛的同学理解“数组下标不一定是序号，也可以是值本身”这个重要思维。我也见过不少刷了几十道题的人，遇到这种题还是下意识写双重循环，根本没有想过可以用一个计数数组把复杂度从O(N^2)降到O(N+M)。如果你也处于这个阶段，不妨静下心把这篇题解看完。我会把题意拆开，把暴力做法和桶计数做法对比清楚，再给一份可以直接提交的C++代码，最后聊聊提交时容易踩的坑。这套“先统计、再查询”的思路，后面找重复元素、求交集、统计分段人数都会反复用到，值得花十几分钟彻底搞懂。

1.1 题目输入输出长什么样

先明确一下输入输出格式，这是所有讨论的前提。输入第一行是两个整数N和M，N是总人数，M是书的编号上限。接下来N行，每行一个1到M范围内的整数，表示第i个人喜欢的书的编号。输出有N行：第i行表示第i个人的潜在朋友个数，如果这个人是0，就输出BeiJu。

举个例子。假设输入是：

code复制5 3
1
2
1
3
1

这里N=5，M=3，5个人分别喜欢书1、2、1、3、1。喜欢书1的人有第1、第3、第5个人，所以他们三个互为潜在朋友，每个人潜在朋友数是2；喜欢书2的只有第2个人，喜欢书3的只有第4个人，这两个人没有潜在朋友，都要输出BeiJu。最终输出是：

code复制2
BeiJu
2
BeiJu
2

注意这里的“潜在朋友”不包含自己。比如第1个人虽然和另外两个人都喜欢书1，但总不能把自己也算成自己的朋友，所以他的朋友数是2而不是3。这个“减一”细节是整道题最容易出错的地方，后面我会专门强调。

1.2 “潜在朋友”拆开看：其实就是同好集合大小减一

把题意抽象一下：每个人有一个属性值，就是喜欢的书编号。潜在朋友的定义是“属性值相同且不是自己本人的人”。如果按书编号把人分成若干组，那么同一组里的人互相都是潜在朋友。假设某本书x一共有cnt[x]个人喜欢，那么其中任意一个人的潜在朋友数量都是cnt[x]-1，因为要排除自己。

从这个角度看，“谁是你的潜在朋友”这个问题，本质上不是在找人与人之间的具体对应关系，而是在统计每个分组的人数，然后逐一回答每个人的组员数量减一。这样的问题天然适合用哈希表或者桶数组解决：第一遍扫描所有人，把喜欢的书编号当作key，累加计数；第二遍再扫描所有人，根据自己那本书的计数算出答案。

这里还有一个容易忽略的点：题目问的是“书编号不超过M”，所以书的编号是连续且有限的。这意味着我们可以直接用数组下标来表示书号，不需要任何复杂的哈希函数。如果书号范围很大，比如1到10^9，那就要换用哈希表，不过本题用数组就够了。

2. 为什么不能只靠双重循环？暴力的复杂度先算一笔账

很多新手拿到这题的第一反应是：直接两两比较嘛，用两层循环数一下每个人和哪些人书号相同不就行了。逻辑上确实没错，但我们刷题不能只看“能不能算对”，还要看“能不能在时限内跑完”。这一节我把暴力做法摆出来，认真算算它的复杂度，你就知道为什么必须换思路了。

2.1 两两比较的思路看起来很简单

最直白的暴力做法是：外层循环枚举每个人i，内层循环枚举所有人j，当j不等于i并且like[i]等于like[j]时，计数器加一。写出来大概是这样：

cpp复制for (int i = 1; i <= n; i++) {
    int cnt = 0;
    for (int j = 1; j <= n; j++) {
        if (i != j && like[i] == like[j]) {
            cnt++;
        }
    }
    cout << cnt << endl;
}

这段代码逻辑完全正确。N很小的时候，比如N=100，两层循环也就一万次，跑起来毫无压力。可题目数据范围不会这么温柔。如果N来到10^4，两层循环就是10^8次比较，已经开始卡时间了；如果N是10^5，那就是10^10次比较，任何OJ都扛不住。更不要说M也可能很大，虽然M对暴力的内层循环没有直接影响，但读入和输出的开销同样可观。

所以这个暴力的时间复杂度是O(N^2)，空间复杂度是O(N)。它的问题在于：做了大量重复比较。第1个人和第2个人比较过一次，第2个人和第1个人又比较一次；而且这种两两比较根本没有利用“书号”这个中间属性，相当于是把所有人拉到一个平面上做全排列匹配，信息浪费很严重。

2.2 换一个视角：书才是连接所有人的“索引”

暴力做法之所以慢，是因为它一直在比较“人”和“人”。但仔细想想，两个人之所以成为潜在朋友，共同点是“喜欢同一本书”。那么书其实就是天然的索引，我们完全可以跳过人和人之间的直接比较，改成“先把人按书归类，再统计每类的大小”。

具体来说就是：扫描所有人，用一个数组cnt记录每本书被多少个人喜欢。cnt[x]表示喜欢书x的人数。这一步只需要O(N)的时间。然后再扫描所有人，对于第i个人来说，他喜欢的书编号是like[i]，喜欢这本书的一共有cnt[like[i]]个人，去掉他自己，答案就是cnt[like[i]]-1。如果这个数是0，就输出BeiJu。整体复杂度是O(N+M)，空间复杂度是O(M)。

两种做法对比一下：

从O(N^2)到O(N+M)，这个提升是数量级的。当N是10^5时，前者要跑10^10次，后者只需要几百万次，差距显而易见。更重要的是，这个“先建索引再回答查询”的思维在真实开发中也非常常见。比如你要统计一份订单列表里每个用户下了多少单，不会用用户和用户两两比较，而是先按用户ID分组再计数，本质上就是同一个模型。

3. 桶计数解法：一次统计加二次查询，代码就这么写

思路清楚了，代码其实很短。这一节我给出完整的C++实现，然后逐段解释为什么这么写，重点说清楚两个关键细节：为什么要减一，为什么要分成两个循环。

3.1 一份可以直接提交的C++代码

这里假设N和M都在10^5以内，数组开大一点就行。如果题目给出的范围更大，把数组上限相应调大即可。

cpp复制#include <iostream>
using namespace std;

const int MAXN = 100005;
const int MAXM = 100005;

int like[MAXN];
int cnt[MAXM];

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

    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> like[i];
        cnt[like[i]]++;
    }

    for (int i = 1; i <= n; i++) {
        int ans = cnt[like[i]] - 1;
        if (ans == 0) {
            cout << "BeiJu" << '\n';
        } else {
            cout << ans << '\n';
        }
    }

    return 0;
}

这个代码在结构上只有两个循环：第一个循环负责读入并统计，第二个循环负责查询并输出。数组like存每个人喜欢的书号，数组cnt以书号为下标，存储对应书号的被喜欢次数。建议把这套代码当成模板记住，因为后面很多“按属性分组统计”的题都可以直接套用这个框架。

3.2 为什么答案必须减一，为什么不能边读边输出

先解释“减一”。cnt[like[i]]统计的是“包括自己在内的、喜欢同一本书的总人数”。潜在朋友数要求的是“其他同样喜欢这本书的人”，所以必须把i自己从总人数里去掉。比如一本书被5个人喜欢，那其中每个人的潜在朋友数都是4。如果不小心输出cnt[like[i]]，所有答案都会比正确答案大1，非常隐蔽。

我在初学的时候犯过一次低级错误：想着反正cnt数组已经统计完了，直接在第二个循环里cout << cnt[like[i]]，结果样例输出总是多1。后来才发现，题目里的“潜在朋友”这个词强调的是“朋友”是别人，不是自己。这个问题如果不通过样例细心排查，很难一眼看出来。

再解释“为什么必须分成两个循环”。有些同学可能会想：能不能在读入第i个人的同时，直接输出第i个人的潜在朋友数？这样做在逻辑上是错的。因为你读第i个人的时候，后面那些人的书号还没进来，cnt数组的统计是不完整的。比如第2个人和第3个人都喜欢书5，当你读完第2个人准备输出时，你只知道第2个人喜欢书5，还不知道第3个人也喜欢书5，此时你算出的答案是0，但正确答案应该是1。所以必须先把所有人读完之后，cnt数组才是最终状态，这时再统一输出才是对的。

这两个细节，一个是“减一”，一个是“两遍循环”，其实就是这道题最容易出问题的两个地方。代码本身不长，把这两点刻在脑子里，基本就不会写错了。

4. 手动验证样例与边界情况，把答案算得明明白白

光贴代码不算完，我习惯在写完题解后用手算几个用例验证一下，尤其是边界情况。这道题的边界情况不多，但每一条都值得单独测一下，能帮你确认代码是不是真的理解了题意。

4.1 完整样例逐行推演

沿用前面1.1里的样例，但把人数扩到6个，让结果更有区分度。假设输入是：

code复制6 4
2
1
2
3
4
2

第一遍统计之后，cnt数组的内容是：cnt[1]=1，cnt[2]=3，cnt[3]=1，cnt[4]=1。现在逐个人计算：

你会看到，第1、3、6个人都喜欢书2，所以他们的潜在朋友数都是2。这个2指的是另外两个同好，不是泛指任意两个朋友。喜欢书1、书3、书4的人都只有自己一个，所以都输出BeiJu。这个推演过程看着繁琐，但它能帮你建立“统计后再查询”的直观印象：朋友数是组内共享的，同一组的人答案完全相同。

4.2 三组边界数据实测

第一组：所有人都喜欢同一本书。如果N=5，M=3，五个人全部喜欢书1，那么统计后cnt[1]=5。每个人输出的答案都是5-1=4。这很合理，因为另外4个人都是潜在朋友。如果你的代码输出5，那基本可以确定是忘记减一了。

第二组：所有人都喜欢不同的书。如果N=4，M=4，四个人分别喜欢书1、2、3、4，那么每个cnt[like[i]]都等于1，答案全是0，也就是所有人都输出BeiJu。这种数据主要用来验证“没有潜在朋友”的输出逻辑是否正确，尤其要注意大小写和拼写，BeiJu不是Beiju，也不是BEIJU。

第三组：N=1，只有一个人。不管他喜欢哪本书，cnt[like[1]]永远是1，潜在朋友数是0，输出BeiJu。这个用例看似简单，却能检验代码能否正确处理“唯一一个人”的情况。有些人在写暴力时会对i==j做特殊判断，反而容易在这里出问题，桶计数解法天然不会踩这个坑。

把这些边界测完，代码的正确性就相当有把握了。如果你在做题软件上WA，建议自己构造这几组数据跑一遍，很多低级错误当场就能暴露出来。

5. 提交时常见的坑和我的排查经验

这题虽然简单，但提交记录里依然能看到各种奇怪的错误。我把平时答疑时遇到的高频问题整理一下，每一种都是我亲眼见过或者亲身踩过的，希望能帮你节省点调试时间。

5.1 输出BeiJu还是数字，最容易翻车的地方

这题的输出要求是“如果没有潜在朋友，输出BeiJu”，注意不是输出0。很多AC代码习惯性写cout << ans，然后发现全0的用例输出的是0，而不是BeiJu，直接WA。反过来，如果你刷的某个版本题目要求输出0，而你写了BeiJu，同样是WA。所以在写之前一定把题面输出说明看清楚，不要想当然。

另外BeiJu的大小写也不能错。这个字符串看起来像拼音，很多人在输入法里一顺手就写成beiju或者BEIJU，OJ对字符串匹配是大小写敏感的，差一个字母都不行。最稳妥的办法是直接从题目描述里复制这个字符串，或者专门记一下，它就是BeiJu四个字母，B大写，J大写，其他小写。这种输出格式的细节，可以说是新手最容易忽略的扣分点。

5.2 数组大小与越界问题

不少人在本地跑得好好的，提交上去却Runtime Error，多半是数组开小了。本题的数组要开到M以上，因为下标直接是书号。如果题目说M最大是10^5，那数组可以开100005，留5个余量。同理，like数组最多存N个人，至少要开N+5。

我自己的习惯是，只要不确定上限，就直接开一个比较大的常量，比如const int MAXN = 1000005，比题目给出的上限多一个数量级。虽然会浪费一点内存，但可以彻底避免越界导致的神秘错误。需要注意的是，如果在函数内部声明大数组，可能会因为栈空间不足而崩溃，所以要么定义成全局变量，要么用vector动态分配。全局数组默认初始化为0，这也是桶计数需要的初始状态。

5.3 多组数据的重置问题

有一些OJ上的题目不会只测一组数据，而是要求循环处理多组输入，直到文件结束。如果题目是这种格式，你就不能只统计一次。常见写法是while (cin >> n >> m)，每处理完一组，下一组开始前必须把cnt数组全部清零，否则上一组残留的计数会和这一组叠加，导致所有答案偏大。

清零可以用memset(cnt, 0, sizeof(cnt))，也可以用fill(cnt, cnt + MAXM, 0)。我第一次刷这类多组输入的题目时，就忘了重置cnt，结果第一组样例对，第二组开始所有数字都大了不少。排查半天才发现是残留数据在作怪。如果你不确定题目是一组还是多组，看一眼输入描述里有没有类似“多组测试数据”的字样，有的话一定要处理重置逻辑。

5.4 输入输出优化：cin能不能用

N和M在10^5这个量级时，cin和cout完全够用。但竞赛环境里数据量一大，默认的cin同步开销就很可观。最稳妥的做法是在main函数开头加上这两行：

cpp复制ios::sync_with_stdio(false);
cin.tie(nullptr);

这会把C++的输入输出绑定关掉，让cin比肩scanf的速度。如果你用的是printf，就没必要管这个。我自己习惯用cin+关同步，因为代码读起来更简洁。有些同学可能觉得题目简单不需要优化，但我见过太多人因为没关同步导致TLE，最后不是算法问题，而是输入输出开销太大。既然是白送的优化，写上总没有坏处。

还有一个常见问题是循环里用endl换行。endl在每次输出时都会强制刷新缓冲区，频繁使用会拖慢速度。更合适的做法是输出'\n'，效果相同但不会刷新缓冲区。这题输出N行，最多10万次，用endl确实能感受到卡顿，换成'\n'会清爽不少。

6. 把“统计频次再查询”的套路带走去刷其他题

最后想聊一点更通用的东西。这道题本身不难，但它背后藏着一个可以迁移到很多题目里的解题套路，值得单独说清楚。这个套路就是：先遍历一遍所有数据，把某个属性值的出现次数统计好，然后再遍历一遍原始数据，对每个元素用统计结果回答具体问题。

6.1 怎么判断一道题能不能用这个套路

当你发现题目想让你“根据某个属性找同类”时，可以先想想：能不能按照属性值把元素分组，然后利用组的大小直接回答每个元素的问题。如果答案是肯定的，那大概率可以用桶数组或哈希表解决。比如“找出一堆数里出现次数最多的数字”，就是先统计频次再遍历找最大值；“判断两个数组的交集”，也是先统计其中一个数组的频次，再遍历另一个数组看哪些值出现过；还有“统计每个分数段的人数”，本质都是在做键值聚合。

判断的关键不是看题目描述用了什么花哨的名词，而是看问题结构。如果题目中每个人都带着一个“标签”，最终要回答的又是每个标签对应的人数或者每个标签下的人，那十有八九就是桶计数。AcWing 3404里，人的标签是喜欢的书号，要回答的正是标签组的人数减一。下次遇到“同好”“同组”“同类”这类关键词，条件反射地往哈希表上想，基本不会错。

6.2 如果书的编号范围大到用不了数组怎么办

本题的M比较温和，可以直接开数组。但有些题目里编号范围可能是10^9甚至更大，或者编号根本就不是整数而是字符串。这时候桶数组就不行了，需要换成哈希表。C++的unordered_map可以完美替代这里的cnt数组，用法几乎一样：

cpp复制#include <unordered_map>
using namespace std;

unordered_map<int, int> cnt;

for (int i = 1; i <= n; i++) {
    cin >> like[i];
    cnt[like[i]]++;
}

for (int i = 1; i <= n; i++) {
    int ans = cnt[like[i]] - 1;
    if (ans == 0) cout << "BeiJu" << '\n';
    else cout << ans << '\n';
}

unoredered_map底层是哈希表，查询和插入的期望时间复杂度都是O(1)，所以总复杂度依然是O(N+M)。区别只是常数略大一点。如果你的编译器环境不支持unordered_map（比如某些古老OJ），退而求其次可以用map，它的插入和查询是O(log M)，在本题数据量下也完全能过。这个替换思路比死记代码重要得多，因为很多题的“编号”不会那么好心地给你一个连续的整数范围。

6.3 如果题目想让你输出具体是哪几个人

有时候题目会升级一下，不止要人数，还想让你把具体是哪些潜在朋友输出出来。这时候计数数组就不够用了，因为cnt只记录了组的大小，没有记录组里具体是谁。解决办法是把cnt数组的类型从int改成vector，让每个书号对应一个动态数组，把人编号塞进去：

cpp复制vector<int> book[MAXM];

for (int i = 1; i <= n; i++) {
    cin >> like[i];
    book[like[i]].push_back(i);
}

for (int i = 1; i <= n; i++) {
    // 遍历喜欢同一本书的人，跳过自己
    for (int p : book[like[i]]) {
        if (p != i) {
            cout << p << ' ';
        }
    }
    cout << '\n';
}

这个做法的思路和桶计数完全一致，只是把“每本书有多少人”升级成“每本书有哪些人”。遍历输出的总次数是所有潜在朋友对的数量，最坏情况下如果所有人都喜欢同一本书，输出规模是N*(N-1)，这是不可避免的，因为题目要求的输出本身就那么大。理解了这个升级版，你就真正掌握了“按属性分组”这个核心思想，以后不管题目问人数、问名单还是问集合关系，都能游刃有余。

最后说一个我刷题时养成的习惯：遇到这种“找同类”的题，先停下来问自己一句，能不能用一个桶把元素按某个属性装起来。桶装完再想每个元素的具体答案，往往就顺理成章了。AcWing 3404作为一道入门题，把这件事演示得特别清楚，把这个套路练熟，后面做中等题会省很多力气。