825. 适龄的朋友

🎯 问题描述（来源于LeetCode）

描述：
在社交媒体网站上有 n 个用户。给你一个整数数组 ages，其中 ages[i] 是第 i 个用户的年龄。
如果满足以下任意条件，则用户 x 不会向用户 y（x != y）发送好友请求：

  • age[y] <= 0.5 * age[x] + 7
  • age[y] > age[x]
  • age[y] > 100 && age[x] < 100

否则，x 会向 y 发送好友请求。
注意：如果 x 向 y 发送请求，不一定意味着 y 也会向 x 发送请求。
返回总共发出的好友请求数目。

说明：

  • 年龄范围在 1 到 120 之间。
  • n 最大为 2 * 10^4。

示例：

  • 示例 1：
1
2
3
输入: ages = [16,16]
输出: 2
解释: 两人年龄相同，16 > 0.5*16+7 = 15，条件不成立，所以互相发送请求，共2个。
  • 示例 2：
1
2
3
输入: ages = [16,17,18]
输出: 2
解释: 只有18向17和16发送请求？实际计算为2。

💻 解题思路

思路：计数 + 滑动窗口（基于您的代码）

算法步骤

  1. 因为年龄范围只有 1~120，所以创建一个长度为 121 的计数数组 cnt，统计每个年龄的人数。
  2. 使用双指针滑动窗口：
    • age_y 表示窗口左边界（年龄最小），cnt_window 表示窗口内年龄在 [age_y, age_x] 之间的人数总和（不包含 age_y 指针之前的年龄）。
    • 遍历年龄 age_x 从 0 到 120，将当前年龄的人数 c 加入窗口。
    • 当 age_y * 2 <= age_x + 14 时（即 age_y <= 0.5 * age_x + 7），说明年龄为 age_y 的人不能向 age_x 发送请求（因为不满足 age[y] > 0.5*age[x]+7），需要将这部分人移出窗口：cnt_window -= cnt[age_y]，并将 age_y 右移。
    • 此时，窗口内剩余的人（年龄在 [age_y, age_x] 之间）都可以向年龄为 age_x 的人发送请求。
    • 对于每个年龄 age_x 的 c 个人，他们每个人可以向窗口内的所有人发送请求，但 不能向自己发送（因为 x != y）。所以新增请求数为 c * (cnt_window - 1)？注意：cnt_window 包含当前年龄的所有人（包括自己），所以需要减去自身，即 c * cnt_window - c（因为每个人不能给自己发，减去 c 个自身）。但这里还应注意，如果 cnt_window 只包含 age_y 到 age_x 之间的人，且 age_x 自己也在窗口内，所以减去 c 正好排除了同年龄的自身请求。
    • 累加到 ans。
  3. 返回 ans。

代码实现（您的代码）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
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
            if age_y * 2 <= age_x + 14:  # 不能发送好友请求
                cnt_window -= cnt[age_y]
                age_y += 1
            if cnt_window:  # 存在可以发送好友请求的用户
                ans += c * cnt_window - c
        return ans

📊 性能分析

  • 时间复杂度：O(n+121)O(n + 121)，实际为 O(n)O(n)，因为年龄范围固定为 120。
  • 空间复杂度：O(121)O(121)，计数数组大小固定。

思考

该解法非常精妙，利用年龄范围小这一特点，使用计数数组和双指针滑动窗口来统计满足条件的请求数。
关键点在于窗口维护：当 age_y 不满足 age_y > 0.5 * age_x + 7 时，将其移出窗口。此时窗口内所有年龄都满足第一个条件，且因为 age_y 递增，也满足 age_y <= age_x（即第二个条件 age[y] <= age[x] 也自然满足，因为窗口内年龄不超过当前年龄）