题目

在社交媒体网站上有 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 发送一条好友请求。另外，用户不会向自己发送好友请求。

返回在该社交媒体网站上产生的好友请求总数。

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/friends-of-appropriate-ages

解答

这道题题意着实杂乱，但理解下来，就是在ages中，当前用户x，发送好友请求的目标，一定是 <= x本身的（见条件2）。

然后条件3的话，其实已经被条件2所包括了，不用额外关注。

条件1的话，是一个硬性条件，规定了比用户x的年龄小的最低值，也就是好友请求一定比这个值大才行。

下面具体看方法：

1. 排序后区间求和

以当前用户 x 为中心，要找的好友是一个区间，右端最大值为 x 本身，左端最小值也要保证大于 0.5*ages[x]+7 。

所以先将ages进行排序，然后从第一个用户开始遍历即可，每个用户所符合的区间，进行相加。

同时，这里有一个坑，就是区间可能不存在，即求出来的左端最小值比 x 本身大，一定要过滤掉。

再具体的理解建议直接看代码。

class Solution {
public:
    int numFriendRequests(vector<int> &ages) {
        int ret = 0;
        int l = 0; // 左区间
        int r = 0; // 右区间
        int n = ages.size();

        // 先进行从小到大的排序
        sort(ages.begin(), ages.end());

        for (auto a: ages) {
            // 避免使用 0.5 的小数
            // ages[l] <= 0.5 * a + 7  可以推导至该公式
            while (2 * ages[l] - 14 <= a) {
                l++;
            }

            while (r + 1 < n && ages[r + 1] <= a) {
                r++;
            }

            // a < 15 的情况下，r会比l小
            if (r < l) {
                continue;
            }

            ret += r - l;
        }

        return ret;
    }
};

2. 前缀和

因为这道题终归是要求一个区间和，可以先统计所有用户年龄的前缀和，即比该用户年龄小的用户一共有多少个。

然后求当前x用户的好友请求数时，用对应的x前缀和减去最小值（区间最左）点对应的前缀和，就是满足条件的数量，再进行相加即可。

class Solution {
public:
    int numFriendRequests(vector<int> &ages) {
        int ret = 0;

        // 1 <= ages[i] <= 120
        vector<int> num(121, 0);
        vector<int> preSum(121, 0);

        // 统计每个年龄的人数
        for (auto i: ages) {
            num[i]++;
        }

        // 求前缀和
        for (int i = 1; i < 121; i++) {
            preSum[i] = preSum[i - 1] + num[i];
        }

        // 依次遍历每个年龄的人
        for (int i = 15; i < 121; i++) {
            if (num[i]) {
                int least = (int) (i * 0.5 + 7) + 1;
                ret += num[i] * (preSum[i] - preSum[least - 1] - 1);
            }
        }

        return ret;
    }
};

3. map记录方法

不需要进行排序，直接记录每一个年龄的用户有多少，然后直接求出左右区间的最大最小值，然后进行map的相加。

class Solution {
public:
    int numFriendRequests(vector<int> &ages) {
        unordered_map<int, int> mp;
        unordered_set<int> pass;
        int ret = 0;

        for (auto i: ages) {
            mp[i]++;
        }

        for (int i = 0; i < ages.size(); ++i) {
            auto it = pass.find(ages[i]);
            if (it == pass.end()) {
                pass.insert(ages[i]);
                int tmp = 0;
                int least = (int) (0.5 * ages[i] + 7) + 1;

                for (int j = least; j < ages[i]; ++j) {
                    auto it2 = mp.find(j);
                    if (it2 != mp.end()) {
                        tmp += it2->second * mp[ages[i]];
                    }
                }
                if (ages[i] >= least) {
                    auto it3 = mp.find(ages[i]);
                    if (it3 != mp.end()) {
                        tmp += it3->second * (it3->second - 1);
                    }
                }
                ret += tmp;
            }
        }
        return ret;
    }
};