适龄的朋友 图解题解

每个人按年龄发好友请求，这道题到底在数什么

给一个年龄数组 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。

Python

from __future__ import annotations
from 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

C++

#include <algorithm>
#include <array>
#include <cctype>
#include <climits>
#include <cmath>
#include <deque>
#include <functional>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
using namespace std;
class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        const int m = 121;
        vector<int> cnt(m);
        for (int x : ages) {
            ++cnt[x];
        }
        int ans = 0;
        for (int ax = 1; ax < m; ++ax) {
            for (int ay = 1; ay < m; ++ay) {
                if (!(ay <= 0.5 * ax + 7 || ay > ax || (ay > 100 && ax < 100))) {
                    ans += cnt[ax] * (cnt[ay] - (ax == ay ? 1 : 0));
                }
            }
        }
        return ans;
    }
};

Java

import java.util.*;
class Solution {
    public int numFriendRequests(int[] ages) {
        final int m = 121;
        int[] cnt = new int[m];
        for (int x : ages) {
            ++cnt[x];
        }
        int ans = 0;
        for (int ax = 1; ax < m; ++ax) {
            for (int ay = 1; ay < m; ++ay) {
                if (!(ay <= 0.5 * ax + 7 || ay > ax || (ay > 100 && ax < 100))) {
                    ans += cnt[ax] * (cnt[ay] - (ax == ay ? 1 : 0));
                }
            }
        }
        return ans;
    }
}