LeetCode 825. 适龄的朋友（计数排序+前缀和）

示例 1：
输入：[16,16]
输出：2
解释：二人可以互发好友申请。

示例 2：
输入：[16,17,18]
输出：2
解释：好友请求可产生于 17 -> 16, 18 -> 17.

示例 3：
输入：[20,30,100,110,120]
输出：3
解释：好友请求可产生于 110 -> 100, 120 -> 110, 120 -> 100.
 
提示：
1 <= ages.length <= 20000.
1 <= ages[i] <= 120.

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        vector<int> age(121, 0);//每个年龄有多少人
        for(auto a : ages) 
            age[a]++;
        vector<int> sum(121,0);
        for(int i = 1; i <= 120; i++)
        {
            sum[i] += sum[i-1]+age[i];// 前缀人数和
        }
        int ans = 0, l, r;
        for(int i = 15; i <= 120; i++)
        {
            l = i/2 + 7;
            r = i;
            ans += (sum[r-1]-sum[l])*age[i]+age[i]*(age[i]-1);
            //  年龄小于当前的，满足条件的人* 每人都可以发
            //  + 当前同龄里的人，互相发，排列 An2
        }
        return ans;
    }
};