825. 适龄的朋友

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

ages[y] <= 0.5 * ages[x] + 7
ages[y] > ages[x]
ages[y] > 100 && ages[x] < 100
否则，x 将会向 y 发送一条好友请求。

注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。

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

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/friends-of-appropriate-ages
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

计数 + 前缀和

class Solution {

    public int numFriendRequests(int[] ages) {
        int[] cnt = new int[121];
        for (int age : ages) {
            cnt[age]++;
        }
        int[] sum = new int[121];
        for (int i = 1; i <= 120; ++i) {
            sum[i] = cnt[i] + sum[i - 1];
        }
        int ans = 0;
        for (int i = 1; i <= 120; ++i) {
            if (cnt[i] > 0) {
                int j = (int) (0.5 * i + 8);
                if (j <= i) {
                    ans += cnt[i] * (sum[i] - sum[j - 1] - 1);
                }
            }
        }
        return ans;
    }
}

排序 + 双指针

import java.util.Arrays;

class Solution {

    /**
     * 0.5 * ages[x] + 7  < ages[y] <= ages[x]
     */
    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int ans = 0;
        int i = 0, j = 0;
        for (int age : ages) {
            if (age < 15) {
                continue;
            }
            while (j < ages.length && ages[j] <= 0.5 * age + 7) {
                j++;
            }
            while (i + 1 < ages.length && ages[i + 1] <= age) {
                i++;
            }
            ans += i - j;
        }
        return ans;
    }
}