825. Friends Of Appropriate Ages _friend

少年辛苦终身事，莫向光阴惰寸功。这篇文章主要讲述825. Friends Of Appropriate Ages相关的知识，希望能为你提供帮助。
问题描述：
Some people will make friend requests. The list of their ages is given and ages[i] is the age of the ith person.
Person A will NOT friend request person B (B != A) if any of the following conditions are true:

age[B] < = 0.5 * age[A] + 7
age[B] > age[A]
age[B] > 100 & & age[A] < 100

Otherwise, A will friend request B.
Note that if A requests B, B does not necessarily request A. Also, people will not friend request themselves.
How many total friend requests are made?
Example 1:

Input: [16,16] Output: 2 Explanation: 2 people friend request each other.

Example 2:

Input: [16,17,18] Output: 2 Explanation: Friend requests are made 17 -> 16, 18 -> 17.

Example 3:

Input: [20,30,100,110,120] Output: Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.

Notes:

1 < = ages.length < = 20000.
1 < = ages[i] < = 120.

解题思路：
一开始想到的是暴力破解法：即O(n2)的方法，但是显然OJ是不会让你过的：）
这里参考了votrubac 的解法
只能说我没有好好分析题意
遇见这种不等式没能去化简

由条件一：

age[B] 
<
= 0.5 * age[A] 
+ 7

和条件二：

age[B] 
>
 age[A]

可得 age[A] < 0.5 * age[A] + 7
即 age[A] < 14
当年龄小于14时，是不可以发出好友请求的。
由于题目限定：

1 <
= ages[i] <
= 120

.
我们可以将每个年龄出现的个数存入一个固定大小的数组（这将花费我们O(n)的时间）
而由于遍历固定大小的数组的时间是一定的，实际上是O(1)

根据我们上面得出的条件：
我们将从年龄为15的开始向后遍历
对当前年龄，我们又可以分为两种情况：
1. 同龄人：cnt[i] * (cnt[i] - 1)
2. 比TA小且满足要求的人：由j = 0.5 * i + 8开始向后遍历，且j < i

【825. Friends Of Appropriate Ages】

代码：

class Solution { public: int numFriendRequests(vector< int> & ages) { int cnt[121] = {}; int ret = 0; for(int a : ages){ cnt[a]++; } for(int i = 15; i < 121; i++){ if(cnt[i] == 0) continue; ret += cnt[i] * (cnt[i]-1); for(int j = 0.5 * i + 8; j < i; j++) ret += cnt[j]*cnt[i]; } return ret; } };