题目描述
思路解析动画文字版
三个条件简化成一个区间:第②条说不能发给比自己大的,第③条其实被第②条包住了(年龄超 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 · 吴师兄开源图解算法，几十万开发者在看的算法讲解
想成体系刷透这类套路？去图解算法专题