在社交媒体网站上有 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：

    输入：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.length
    1 <= n <= 2 * 104
    1 <= ages[i] <= 120

    排序＋双指针

    1. class Solution {
    2.     /**
    3.     我们可以先对 ages 进行排序，枚举每个 y = ages[i]，同时使用 l 和 r 维护左右区间，[l, r)[l,r) 代表在 ages 上会往 y = ages[i] 发送请求的 xx 连续段，统计每个 y = ages[i] 的 xx 有多少个即是答案，同时需要注意在 [l,r) 范围内是包含 y = ages[i] 自身，统计区间长度时需要进行 r-l−1 操作。
    4.     O(nlogn) O(logn)
    5.      */
    6.     public int numFriendRequests(int[] ages) {
    7.         Arrays.sort(ages);
    8.         int n = ages.length;
    9.         int res = 0;
    10.         int l = 0, r = 0;
    11.         for (int i = 0; i < n; ++i) {
    12.             while (l < i && !check(ages[l],ages[i])) l++;
    13.             if (r < i) r = i;
    14.             while (r < n && check(ages[r],ages[i])) r++;
    15.             if (l < r) res += r - l - 1;
    16.         }
    17.         return res;
    18.     }
    19.     public boolean check(int x, int y) {
    20.         if (y <= 0.5 * x + 7) return false;
    21.         if (y > x) return false;
    22.         if (y > 100 && x < 100) return false;
    23.         return true;
    24.     }
    25. }

    桶排序+前缀和 O（max(n,c)) 空间Oc

    1. class Solution {
    2.     public int numFriendRequests(int[] ages) {
    3.         int N = 130;
    4.         int[] sum = new int[N];
    5.         //桶排序
    6.         for (int i : ages) sum[i]++;
    7.         //前缀和
    8.         for (int i = 1; i < N; ++i) sum[i] += sum[i-1];
    9.         int res = 0;
    10.         for (int x = 1, y = 1; y < N; ++y) {
    11.             int a = sum[y] - sum[y-1];  //a个y
    12.             if (a == 0) continue;
    13.             if (x < y) x = y;
    14.             while (x < N && check(x,y)) x++;
    15.             int b = sum[x-1] - sum[y-1] - 1;    //b个x
    16.             if (b > 0) res += a * b;
    17.         }
    18.         return res;
    19.     }
    20.     public boolean check(int x, int y) {
    21.         if (y <= 0.5 * x + 7) return false;
    22.         if (y > x) return false;
    23.         if (y > 100 && x < 100) return false;
    24.         return true;
    25.     }
    26. }