在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。
如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：
ages[y] <= 0.5 * ages[x] + 7ages[y] > ages[x]ages[y] > 100 && ages[x] < 100
否则，x 将会向 y 发送一条好友请求。
注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。
返回在该社交媒体网站上产生的好友请求总数。
示例 1：
输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。示例 2：
输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。示例 3：
输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。提示：
n == ages.length1 <= n <= 2 * 1041 <= ages[i] <= 120
解题思路一：排序 + 双指针
首先根据题目给的 x 不能给 y 发送请求的条件中，第三点其实已经被包含在了第二点中了！
所以 x 能给 y 发送请求的条件为 0.5 * ages[x] + 7 < ages[y] <= ages[x]。
这里还能再推导一下 x 的起始范围，因为 0.5 * ages[x] + 7 < ages[x]，所以就能得到 14 < ages[x]，因此我们只需要考虑 ages[x] >= 15 的情况，此时满足 ages[y] 的范围为 ( 0.5*ages[x]+7, ages[x] ]，在实际编程中，我们会用 left 和 right 两个变量来标记这对左右边界！
那么为了满足 ages[x] 增加的时候，ages[y] 能通过双指针控制一个范围来达到发送条件，那么就得让序列是递增的，所以我们要给数组进行排序！
然后从后往前枚举 ages[x]，可保证 ages[x] 前面的元素 ages[y] 全都满足 ages[x] >= ages[y]，因此只需判断前面的元素，ages[y] 是否符合 0.5 * ages[x] + 7 < ages[y] 即可！
根据有序性，可知第一个大于 0.5 * ages[x] + 7 的元素到 ages[x] 全都为符合条件的 ages[y]。
因此，要得出 x 能发多少消息，只需统计有多少满足条件的 y 即可！注意要减去一，因为在这段区间内包含了 ages[x] 本身，所以要减掉！但是因为在实际编程中我们用的是 下标 right - left + 1，其最后减去一之后就是 right - left，不要误以为是没有减去一！
并且注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。 其实这句话是多余的，在 ages[x] != ages[y] 的情况下，满足 x 向 y 发送好友请求的条件，一定不满足 y 向 x 发送好友请求的条件。
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
// 从小到大排序
sort(ages.begin(), ages.end());
int left = 0, right = 0; // 允许发送请求的左右边界
int ret = 0;
for(int x = 0; x < ages.size(); ++x)
{
// 先找到 ages[x] > 14 的位置再开始
if(ages[x] <= 14)
continue;
// 定位左边界
while(ages[left] <= 0.5*ages[x] + 7)
++left;
// 定位右边界 -- 注意判断越界，另外加一因为我们只需要找到ages[x]之前包括ages[x]的右边界
while(right + 1 < ages.size() && ages[right + 1] <= ages[x])
++right;
// 累加计算出的该范围的个数
ret += right - left;
}
return ret;
}
};复杂度分析
- 时间复杂度：，这是排序所需要的时间
- 空间复杂度：，这是排序需要的栈空间
解题思路二：计数排序 + 前缀和
因为这道题的数据范围是 [1, 120]，所以其实我们完全可以用计数排序，其实也就是一个简单的哈希映射，创建一个大小为 120 的数组 count，然后将 ages 数组中的每个年龄的人映射到 count 中去，count[i] 就表示该年龄的人数！
为什么要用计数排序❓❓❓
想必这是很多人的疑惑，其实我们从题解一就能看到，x 能发送请求的数据段其实是连续的，并且是根据升序序列排布的，此时我们使用计数排序，相当于是把可能出现同种年龄的人压缩后都放到了一个桶中，用下标
i来表示年龄的大小，用count[i]来表示该年龄的人数是多少！ 这样子我们遍历一个年龄段的人，不需要遍历多次，只需要遍历一格就能得到其人数有多少！
然后映射之后就是用一个 “前缀和” 技巧，每个位置累加一下之前的人数数量提高计算的速度，为什么要这么做呢❓❓❓
如上图所示，假设我们不使用 “前缀和”，我们发现还是需要去遍历中间这段蓝色的区间获取人数的总和，这样子无非只是比双指针稍微少遍历了几格，优势何在，对不对！
如果先做预处理，使用上 “前缀和“ 技巧，不说得那么高级，其实就是一个累加，每一步都累加上前面出现的人数的总人数，如下所示：
但是我们还是需要留下原来的 count 数组的，因为我们需要判断某个年纪是否有人，如果某个年纪没有人的话，是不需要去累加的这段的！
还要注意的是，我们这里计算出来的蓝色区间的发送人数，只是 right 位置该年龄中的一个人的发送人数，但是该年龄可能存在多个人，所以我们要用 arr[right] - arr[left - 1] - 1 乘以 count[right]，才能算是 right 该年龄中全部人的发送次数！
还有其它的一些细节，参考下面的代码：
class Solution {
public:
int numFriendRequests(vector<int>& ages) {
// 统计各年龄出现的人数
int count[121] = { 0 };
for(int i = 0; i < ages.size(); ++i)
count[ages[i]]++;
// 进行前缀累加处理
int prefix[121] = { 0 };
for(int i = 1; i < 121; ++i) // 这里从1开始遍历，因为不存在年龄为0的人
prefix[i] = prefix[i - 1] + count[i];
// 累加各区域的出现人数总和，从15开始遍历，因为15岁之前不允许发送请求
int ret = 0;
for(int i = 15; i < 121; ++i)
{
if(count[i] != 0)
{
// 这里left中是加8，而不是加7，因为我们的数组在开头多开了一个虚拟位置，整体往后移动了一格
int left = 0.5*i + 8;
// 这里要乘以count[i]是因为前面这部分只是i位置桶中其中一个用户发给其它位置的，但是桶中可能有多个用户，所以要乘以该年龄的桶中的用户数量
ret += (prefix[i] - prefix[left - 1] - 1) * count[i];
}
}
return ret;
}
};