825. Friends Of Appropriate Ages

O(n+A²) time O(A) space
先统计每个年龄的频数，然后两两比较各个年龄
这个题里的第三个条件是没用的，因为第二个条件比第三个条件更严格

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        int m[121] = {0};
        for (int a : ages) {
            ++m[a];
        }
        int res = 0;
        for (int a = 1; a < 121; ++a) {
            if (m[a] == 0) continue; // 没有这个年龄的人，跳过看下一个
            for (int b = 1; b <= a; ++b) { // 这里b > a是不符合条件的，所以上限设成a就行
                if (m[b] == 0 || a >= 2 * b - 14) continue; // 如果b不符合条件则跳过看下一个
                res += m[a] * m[b]; // 如果a和b年龄符合条件则所有a年龄的人都可以request年龄b的人
                if (a == b) { // 如果a年龄和b年龄一样，则要减去自身，因为自己不能request自己
                    res -= m[a];
                }
            }
        }
        return res;
    }
};

O(nlogn) time O(n) space

class Solution {
public:
    int numFriendRequests(vector<int>& ages) {
        sort(begin(ages), end(ages));
        vector<int> t;
        for (int a : ages) {
            t.push_back(2 * a - 14);
        }
        int res = 0, n = t.size();
        for (int i = 0; i < n; ++i) {
            auto it1 = upper_bound(begin(t), end(t), 2 * ages[i] - 14); // B <= A(2B-14 <= 2A-14)
            auto it = upper_bound(begin(t), it1, ages[i]); // A < 2 * B - 14
            res += max(0, int(distance(it, it1) - 1)); // 因为找B <= A时找的上界多算了一个B，所以要减1
        }
        return res;
    }
};