825.适龄的朋友.md

方法一：暴力

class Solution {
    public int numFriendRequests(int[] ages) {
        int cnt = 0;
        int n = ages.length;
        int[][] graph = new int[n][n];
        for (int i = 0; i < n; i++) {
            graph[i][i] = 1;
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (i == j) continue;
                if (ages[j] <= 0.5 * ages[i] + 7 || ages[j] > ages[i] || (ages[j] > 100 && ages[i] < 100)) continue;
                graph[i][j] = 1;
                cnt++;
            }
        }
        return cnt;
    }
}

方法二：排序 + 双指针

在方法一中的想法是算 每个人都会给谁发送好友请求，但是在这种方法中对这种想法进行一下反转，也就是不是看每个人给谁发送请求，而是看每个人都会收到哪些请求。

从题意中我们看出，每个人只会接收到和他同龄或者比他年龄大但是在一定范围内的人发送的请求，可以使用双指针 i 、j。 i 指向和他同龄的第一个人的位置，j 指向比他大但是年龄依然符合要求的最后一个人的位置，那 i ~ j 这个区间内的人就都可以给当前这个人发送好友请求。

如果我们进行了排序，那么就会发现年龄是非递减的，也就是后面的一个人的年龄是大于等于当前这个人的年龄的，那么他的左右指针相比前一个人的左右指针要么不动，要么就向右移动。

class Solution {
    public int numFriendRequests(int[] ages) {
        int res = 0;
        Arrays.sort(ages);
        for (int k = 0, i = 0, j = 0; k < ages.length; k++) {
            while (i < k && !check(ages[i], ages[k])) i++;
            if (j < k) j = k;
            while (j < ages.length && check(ages[j], ages[k])) j++;
            if (j > i) res += (j - i - 1);
        }
        return res;
    }

    public boolean check(int x, int y) {
        if (y <= 0.5 * x + 7 || y > x || (y > 100 && x < 100)) return false;
        return true;
    }
}

方法三：桶排序 + 前缀和

在方法二里可以发现最左端的值和当前值相同，所以可以在桶排序中可以直接使用当前值的位置代替左指针，只要找到右指针就好了，然后判断这之间一共有多少个用户会给当前用户发送请求，然后再乘以和当前用户同龄的用户数即可，因为对于年龄相同的人来说所面对的请求情况都是相同的。

class Solution {
    public int numFriendRequests(int[] ages) {
        int N = 130;
        int[] nums = new int[N];
        for (int age : ages) nums[age]++; // 对年龄进行桶排序
        for (int i = 1; i < 130; i++) nums[i] += nums[i - 1];
        int res = 0;
        for (int y = 1, x = 1; y < N; y++) {
            int a = nums[y] - nums[y - 1];  // y 这个年龄的用户不存在
            if (a == 0) continue;
            if (x < y) x = y;
            while (x < N && check(x, y)) x++;  // z
            int num = nums[x - 1] - nums[y - 1] - 1;
            if (num > 0) res += a * num;
        }
        return res;
    }

    boolean check(int x, int y) {
        if (y <= 0.5 * x + 7 || y > x || (y > 100 && x < 100)) return false;
        return true;
    }
}