题目描述
思路解析
一句话答案：LeetCode 825 适龄的朋友求一共发出多少条好友请求：把三条排除线并成区间 (0.5·x+7, x]，年龄只有 1~120 种，用计数桶让年龄两两统计，把 O(n²) 压到 O(n+120²)。
每个人按年龄发好友请求，这道题到底在数什么
给一个年龄数组 ages，ages[i] 是第 i 人的年龄。用户 x 会向另一人 y 发好友请求，除非踩中三条排除线之一：ay ≤ 0.5·ax+7、ay ＞ ax、或 ay ＞ 100 且 ax ＜ 100（ax、ay 是两人年龄）。三条都不踩才发得出，问全网共发多少条。题面 ages=[16,16] 答案 2，两个 16 岁的人互相都发得出。
两两都比一遍，人一多就比到停不下来
最直白的做法是把每一对 (x, y) 都取出来、逐对套那三条排除线判一次能不能发。可 ages 长度能到两万，两两配对就是四亿次判断，根本跑不动。慢就慢在我们盯着「人」在配对，而人数 n 没有上限可言。
三条排除线其实只圈出一个区间，年龄又只有 120 种
先把三条线并成一句话：x 能发给 y，只需 y 落在区间 (0.5·x+7, x] 里，下界要严格大于、不能取等。第③条 ay ＞ 100 且 ax ＜ 100 其实白给：这种情形 ay 必然大于 ax，已被第②条挡掉。真正省事的在另一头：年龄只落在 1 到 120 之间，共 120 种。既然能不能发只跟年龄有关、跟是谁无关，就别盯着两万个人，改成按年龄分组、让年龄两两配对，把 O(n²) 换成 O(120²) 的固定开销。
按年龄开一个计数桶，再让年龄两两结算
先扫一遍 ages 填计数桶 cnt——cnt[a] 是年龄正好为 a 的人数。再两层循环遍历发送方年龄 ax 和接收方年龄 ay（1 到 120）：ay 落在有效区间就能发，累加 cnt[ax] × cnt[ay] 条。只需小心 ax 等于 ay 那格：同龄可互发但不能发给自己，接收人减掉本人，累加 cnt[ax] × (cnt[ax] − 1)。合起来就是 cnt[ax] × (cnt[ay] − int(ax == ay))。
题面两组数据，各自把请求数结算出来
先看 ages=[16,16]：两人都 16 岁，cnt[16]=2。发送方 16 的有效区间 (0.5·16+7, 16] = (15, 16]，接收方 16 岁落在里面。同龄减本人，每人发给另外 1 个，共 2 条。
再看 ages=[20,30,100,110,120]。20、30、100 岁的区间里都只有自己，各发 0 条；110 岁区间 (62,110] 里还有 100 岁，发 1 条（110→100）；120 岁区间 (67,120] 里有 100 和 110 岁，发 2 条（120→100、120→110）。合计 0+0+0+1+2 = 3，正是题面给的 3。
下界那条线严格大于，同龄那格记得抠掉自己
复杂度上，统计人数 O(n)、两层年龄循环固定 O(120²)，合起来 O(n + 120²)，空间只一个长度 121 的桶。两处最伤答案的细节都在边界：下界是严格大于 0.5·x+7，等于这个值也要挡在外面，若写成 ay ≥ 0.5·x+7 才排除，就会把边界那档人错放进来、多数出请求；ax 等于 ay 那格必须减本人，漏了同龄组每人都算成能发给自己，人数虚高。单人时区间里除自己没别人，答案是 0。
▶ 动画逐步走查（文字版）——想跟着上方动画一帧帧对照就展开
三个条件简化成一个区间:第②条说不能发给比自己大的,第③条其实被第②条包住了(年龄超 100 的一定比小于 100 的大,已经被②挡掉)。所以真正起作用的就是 (0.5·x+7, x]。
先把人按年龄分组:这就是计数桶。上方一排是不同年龄,右侧表是每个年龄各有几个人。接下来对每个年龄当发送方,逐一算它能发出多少请求。
轮到年龄 18 当发送方(紫色)。它只能发给年龄在 (16, 18] 里的人:既要大于 16,又不能超过自己 18。下面逐个桶检查谁落在这个区间里。
检查到自己这组年龄 18:同龄之间互发是允许的,但不能发给自己,所以 2 个人里只能收 1 个(减掉本人)。绿色标记区间内有效。
结算年龄 18 这组:每个人能发 1 条,这组有 2 人,一共贡献 2 条请求。总数累计到 2。
轮到年龄 25 当发送方(紫色)。它只能发给年龄在 (19.5, 25] 里的人:既要大于 19.5,又不能超过自己 25。下面逐个桶检查谁落在这个区间里。
检查年龄 18:它没有超过下界 19.5,会被第①条「ages[y] ≤ 0.5·x+7」挡掉,发不出去(标灰)。
检查到自己这组年龄 25:同龄之间互发是允许的,但不能发给自己,所以 1 个人里只能收 0 个(减掉本人)。绿色标记区间内有效。
年龄 25 这组:有效区间里除了自己没别人可发,每人能发 0 条,这组贡献 0 条。总数仍是 2。
轮到年龄 30 当发送方(紫色)。它只能发给年龄在 (22, 30] 里的人:既要大于 22,又不能超过自己 30。下面逐个桶检查谁落在这个区间里。
检查年龄 18:它没有超过下界 22,会被第①条「ages[y] ≤ 0.5·x+7」挡掉,发不出去(标灰)。
检查年龄 25:它大于下界 22,落在有效区间里(标绿)。这组 1 人每个都能成为接收方。
检查到自己这组年龄 30:同龄之间互发是允许的,但不能发给自己,所以 1 个人里只能收 0 个(减掉本人)。绿色标记区间内有效。
结算年龄 30 这组:每个人能发 1 条,这组有 1 人,一共贡献 1 条请求。总数累计到 3。
轮到年龄 40 当发送方(紫色)。它只能发给年龄在 (27, 40] 里的人:既要大于 27,又不能超过自己 40。下面逐个桶检查谁落在这个区间里。
检查年龄 18:它没有超过下界 27,会被第①条「ages[y] ≤ 0.5·x+7」挡掉,发不出去(标灰)。
检查年龄 25:它没有超过下界 27,会被第①条「ages[y] ≤ 0.5·x+7」挡掉,发不出去(标灰)。
检查年龄 30:它大于下界 27,落在有效区间里(标绿)。这组 1 人每个都能成为接收方。
检查到自己这组年龄 40:同龄之间互发是允许的,但不能发给自己,所以 2 个人里只能收 1 个(减掉本人)。绿色标记区间内有效。
结算年龄 40 这组:每个人能发 2 条,这组有 2 人,一共贡献 4 条请求。总数累计到 7。
把四个年龄组各自贡献的请求数加起来:2 + 0 + 1 + 4 = 7。这就是全网产生的好友请求总数。
回放一遍:全程没有两两枚举,只是按年龄分桶 + 对每个年龄查一次有效区间。年龄种类最多 121 种,所以无论多少人,统计都很快。最终答案 7。
边界先想清:单人 0 条;同龄成对时区间含自己,减掉本人后还能互发。
两个高频追问:排序+二分是等价替代;第③条冗余是这题最爱考的观察点。
参考代码
from __future__ import annotationsfrom typing import *from collections import *from functools import *from itertools import *from math import *from heapq import *from bisect import *class Solution: def numFriendRequests(self, ages: List[int]) -> int: cnt = [0] * 121 for x in ages: cnt[x] += 1 ans = 0 for ax, x in enumerate(cnt): for ay, y in enumerate(cnt): if not (ay <= 0.5 * ax + 7 or ay > ax or (ay > 100 and ax < 100)): ans += x * (y - int(ax == ay)) return ans复杂度
- 时间：O(n + A²)，n 统计人数,A=121 是年龄上限,两层年龄循环与人数无关
- 空间：O(A)，一个长度 121 的计数桶
易错点
面试追问把动画讲成自己的话
追问能不能不用 121×121,而是排序后用二分或双指针?
追问第③条 ages[y] > 100 且 ages[x] < 100 真的可以忽略吗?
这道题到这就讲完了。动画和文字是同一套思路——别光看，关掉页面自己默写一遍。然后顺着主线继续：
山脉数组的峰顶索引
LeetCode 852 · 中等 · 沿着 二分套路 继续往下推进
把这道题真正学会，再走
图解算法年卡 ¥99 /年
- ✓本题每步动画的吴师兄语音讲解（全站陆续覆盖）
- ✓小欧带 8 步通关训练——追问到不看答案也能写对、能 30 秒讲给面试官听
- ✓学习报告，记录每道题的掌握程度
76k+ GitHub Star · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题