文章目錄

• • 1. 題目
  • 2. 解題

1. 題目

人們會互相發送好友請求，現在給定一個包含有他們年齡的數組，ages[i] 表示第 i 個人的年齡。

當滿足以下任一條件時，A 不能給 B（A、B不為同一人）發送好友請求：

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

否則，A 可以給 B 發送好友請求。

注意如果 A 向 B 發出了請求，不等于 B 也一定會向 A 發出請求。
而且，人們不會給自己發送好友請求。

求總共會發出多少份好友請求?

示例 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.

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/friends-of-appropriate-ages
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

• 根據條件，只有從15歲開始才可以發送申請
• 先計數排序，并計算前綴人數和
• 每個年齡段的人分成兩部分：給自己小的年齡的人發，同齡人互發

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;} };

84 ms 28.6 MB

---

我的CSDN博客地址 https://michael.blog.csdn.net/

長按或掃碼關注我的公眾號（Michael阿明），一起加油、一起學習進步！

總結

以上是生活随笔為你收集整理的LeetCode 825. 适龄的朋友（计数排序+前缀和）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。