适龄的朋友 图解题解

这道题到底在问什么

输入

ages=[16,16]

输出

2 (两人互发)

输入

ages=[20,30,100,110,120]

输出

3 (110→100,120→110,120→100)

先想最直接的笨办法

回放一遍:全程没有两两枚举,只是按年龄分桶 + 对每个年龄查一次有效区间。年龄种类最多 121 种,所以无论多少人,统计都很快。最终答案 7。（动画第 24 步）

最优解：一步一步想明白

1. 3三个条件简化成一个区间:第②条说不能发给比自己大的,第③条其实被第②条包住了(年龄超 100 的一定比小于 100 的大,已经被②挡掉)。所以真正起作用的就是 (0.5·x+7, x]。
2. 4先把人按年龄分组:这就是计数桶。上方一排是不同年龄,右侧表是每个年龄各有几个人。接下来对每个年龄当发送方,逐一算它能发出多少请求。
3. 5轮到年龄 18 当发送方(紫色)。它只能发给年龄在 (16, 18] 里的人:既要大于 16,又不能超过自己 18。下面逐个桶检查谁落在这个区间里。
4. 6检查到自己这组年龄 18:同龄之间互发是允许的,但不能发给自己,所以 2 个人里只能收 1 个(减掉本人)。绿色标记区间内有效。
5. 7结算年龄 18 这组:每个人能发 1 条,这组有 2 人,一共贡献 2 条请求。总数累计到 2。
6. 8轮到年龄 25 当发送方(紫色)。它只能发给年龄在 (19.5, 25] 里的人:既要大于 19.5,又不能超过自己 25。下面逐个桶检查谁落在这个区间里。
7. 9检查年龄 18:它没有超过下界 19.5,会被第①条「ages[y] ≤ 0.5·x+7」挡掉,发不出去(标灰)。
8. 10检查到自己这组年龄 25:同龄之间互发是允许的,但不能发给自己,所以 1 个人里只能收 0 个(减掉本人)。绿色标记区间内有效。
9. 11年龄 25 这组:有效区间里除了自己没别人可发,每人能发 0 条,这组贡献 0 条。总数仍是 2。
10. 12轮到年龄 30 当发送方(紫色)。它只能发给年龄在 (22, 30] 里的人:既要大于 22,又不能超过自己 30。下面逐个桶检查谁落在这个区间里。
11. 13检查年龄 18:它没有超过下界 22,会被第①条「ages[y] ≤ 0.5·x+7」挡掉,发不出去(标灰)。
12. 14检查年龄 25:它大于下界 22,落在有效区间里(标绿)。这组 1 人每个都能成为接收方。
13. 15检查到自己这组年龄 30:同龄之间互发是允许的,但不能发给自己,所以 1 个人里只能收 0 个(减掉本人)。绿色标记区间内有效。
14. 16结算年龄 30 这组:每个人能发 1 条,这组有 1 人,一共贡献 1 条请求。总数累计到 3。
15. 17轮到年龄 40 当发送方(紫色)。它只能发给年龄在 (27, 40] 里的人:既要大于 27,又不能超过自己 40。下面逐个桶检查谁落在这个区间里。
16. 18检查年龄 18:它没有超过下界 27,会被第①条「ages[y] ≤ 0.5·x+7」挡掉,发不出去(标灰)。
17. 19检查年龄 25:它没有超过下界 27,会被第①条「ages[y] ≤ 0.5·x+7」挡掉,发不出去(标灰)。
18. 20检查年龄 30:它大于下界 27,落在有效区间里(标绿)。这组 1 人每个都能成为接收方。
19. 21检查到自己这组年龄 40:同龄之间互发是允许的,但不能发给自己,所以 2 个人里只能收 1 个(减掉本人)。绿色标记区间内有效。
20. 22结算年龄 40 这组:每个人能发 2 条,这组有 2 人,一共贡献 4 条请求。总数累计到 7。
21. 23把四个年龄组各自贡献的请求数加起来:2 + 0 + 1 + 4 = 7。这就是全网产生的好友请求总数。
22. 24回放一遍:全程没有两两枚举,只是按年龄分桶 + 对每个年龄查一次有效区间。年龄种类最多 121 种,所以无论多少人,统计都很快。最终答案 7。

⚠️ 容易写错的地方

完整代码（Python / C++ / Java）

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

#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;
    }
};

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;
    }
}

复杂度

面试官可能追问