好友请求的总数（LeetCode 825）
题目描述
某社交平台规定，用户 A 可以向用户 B 发送好友请求需满足以下条件：
- 用户 A 的年龄不小于用户 B 的年龄。
- 用户 B 的年龄大于
0.5 * 用户 A 的年龄 + 7。 - 用户 B 的年龄小于等于用户 A 的年龄。
此外，一个用户不能向自己发送好友请求。
输入：
一个整数数组 ages，表示每个用户的年龄。
输出：
一个整数，表示好友请求的总数。
示例
示例 1
输入：
ages = [16, 16]
输出：
2
解释：
- 两个用户均为 16 岁，他们可以互相发送好友请求。
示例 2
输入：
ages = [16, 17, 18]
输出：
2
解释：
- 用户 16 岁向 16 岁和 17 岁发送好友请求。
- 用户 17 岁只能向 16 岁发送好友请求。
- 用户 18 岁可以向 17 岁发送好友请求。
解题思路
分析条件
根据题目中的条件，我们需要逐步分析满足好友请求的条件：
- 用户 A 的年龄不小于用户 B 的年龄（
ages[A] >= ages[B]）。 - 用户 B 的年龄满足
ages[B] > 0.5 * ages[A] + 7。 - 用户 B 的年龄小于等于用户 A 的年龄（此条件已隐含在条件 1 中）。
优化思路
1. 计数统计
由于用户的年龄范围限制为 1 至 120，我们可以用一个数组 cnt 来统计每个年龄的出现次数。这样，可以避免对每对用户进行暴力比较。
2. 滑动窗口
当我们枚举用户 A 的年龄 ageX 时，需要知道哪些年龄的用户可以成为好友请求的接收者：
- 最小年龄
ageY = 0.5 * ageX + 7。 - 接收者的年龄范围
[ageY, ageX]。
因为 ageX 递增时，ageY 也递增，因此可以通过滑动窗口方法高效统计区间内的用户数。
3. 好友请求数计算
对于每个年龄 ageX：
- 如果该年龄的人数为
cnt[ageX]，区间内人数为cnt_window：- 该年龄的用户可以向
cnt_window人发送好友请求。 - 由于一个用户不能向自己发送请求，因此需要减去
cnt[ageX]。
- 该年龄的用户可以向
- 更新总的好友请求数为：
cnt[ageX] * cnt_window - cnt[ageX]
实现代码
Python 解法
from typing import List
class Solution:
def numFriendRequests(self, ages: List[int]) -> int:
# 统计每个年龄的用户数量
cnt = [0] * 121
for age in ages:
cnt[age] += 1
ans = 0 # 总好友请求数
cnt_window = 0 # 当前窗口内的用户总数
age_y = 0 # 最小年龄下界
for age_x, c in enumerate(cnt): # 遍历每个年龄
cnt_window += c # 当前年龄加入窗口
while age_y * 2 <= age_x + 14: # 不满足好友请求条件
cnt_window -= cnt[age_y]
age_y += 1
if cnt_window > 0: # 存在可以发送好友请求的用户
ans += c * cnt_window - c
return ans
复杂度分析
时间复杂度
- 遍历
ages数组构造计数数组cnt：O(n)。 - 遍历所有可能的年龄范围
[0, 120]：O(U)，其中U = 121是年龄的最大值。 - 滑动窗口中每个年龄至多移动一次：总复杂度为
O(U)。
综合时间复杂度为 O(n + U)。
空间复杂度
- 使用了一个大小为
121的计数数组cnt：O(U)。
综合空间复杂度为 O(U)。
示例解析
示例 1
输入：
ages = [16, 16]
执行过程：
- 构造计数数组：
cnt = [0, 0, ..., 2, ..., 0]（索引 16 对应值为 2）。 - 滑动窗口遍历：
ageX = 16：窗口内包含用户{16}，满足条件人数为2 - 1 = 1。
- 总好友请求数：
2 * 1 = 2。
输出：
2
示例 2
输入：
ages = [16, 17, 18]
执行过程：
- 构造计数数组：
cnt = [0, ..., 1, 1, 1, ..., 0]（索引 16、17、18 对应值为 1）。 - 滑动窗口遍历：
ageX = 16：窗口内包含用户{16}，无其他满足条件用户。ageX = 17：窗口内包含用户{16, 17}，满足条件人数为1。ageX = 18：窗口内包含用户{16, 17, 18}，满足条件人数为2。
- 总好友请求数：
0 + 1 + 1 = 2。
输出：
2
扩展思考题
修改条件为：
0.5 * ages[A] + 7 < ages[B] ≤ 2 * ages[A]
要满足新的条件：
- 接收者的最大年龄需为
2 * ages[A]。 - 滑动窗口调整为
[ageY, 2 * ageX]。 - 当
ageX增加时，滑动窗口右边界也需动态调整。
代码略作修改即可完成。
总结
本题的关键在于：
- 利用计数数组减少冗余计算，避免暴力枚举用户对的复杂度。
- 滑动窗口的巧妙应用，高效统计年龄区间内的人数。
- 数学分析确保满足好友请求条件，结合乘法原理计算请求总数。