Add solution

halfrost · halfrost · commit 5e2df33c5457 · 2022-01-10T22:56:30.000-08:00
diff --git a/leetcode/0825.Friends-Of-Appropriate-Ages/825. Friends Of Appropriate Ages.go b/leetcode/0825.Friends-Of-Appropriate-Ages/825. Friends Of Appropriate Ages.go
@@ -2,12 +2,25 @@ package leetcocde
 
 import "sort"
 
-// 解法一
+// 解法一 前缀和，时间复杂度 O(n)
 func numFriendRequests(ages []int) int {
-	return 0
+	count, prefixSum, res := make([]int, 121), make([]int, 121), 0
+	for _, age := range ages {
+		count[age]++
+	}
+	for i := 1; i < 121; i++ {
+		prefixSum[i] = prefixSum[i-1] + count[i]
+	}
+	for i := 15; i < 121; i++ {
+		if count[i] > 0 {
+			bound := i/2 + 8
+			res += count[i] * (prefixSum[i] - prefixSum[bound-1] - 1)
+		}
+	}
+	return res
 }
 
-// 解法二 双指针 + 排序 O(n logn)
+// 解法二 双指针 + 排序，时间复杂度 O(n logn)
 func numFriendRequests1(ages []int) int {
 	sort.Ints(ages)
 	left, right, res := 0, 0, 0
diff --git a/leetcode/0825.Friends-Of-Appropriate-Ages/README.md b/leetcode/0825.Friends-Of-Appropriate-Ages/README.md
@@ -64,14 +64,56 @@ Explanation: Friend requests are made 110 -> 100, 120 -> 110, 120 -> 100.
 
 ## 解题思路
 
-- 简单题。先统计 [1,120] 范围内每个年龄的人数。然后利用题目中的三个判断条件，筛选符合条件的用户对。需要注意的是，相同年龄的人可以相互发送好友请求。不同年龄的人发送好友请求是单向的，即年龄老的向年龄轻的发送好友请求，年龄轻的不会对年龄老的发送好友请求。
+- 解法三，暴力解法。先统计 [1,120] 范围内每个年龄的人数。然后利用题目中的三个判断条件，筛选符合条件的用户对。需要注意的是，相同年龄的人可以相互发送好友请求。不同年龄的人发送好友请求是单向的，即年龄老的向年龄轻的发送好友请求，年龄轻的不会对年龄老的发送好友请求。
+- 解法二，排序 + 双指针。题目给定的 3 个条件其实是 2 个。条件 3 包含在条件 2 中。条件 1 和条件 2 组合起来是 `0.5 × ages[x]+7 < ages[y] ≤ ages[x]`。当 ages[x] 小于 15 时，这个等式无解。考虑到年龄是单调递增的，`(0.5 × ages[x]+7,ages[x]]` 这个区间左右边界也是单调递增的。于是可以用双指针维护两个边界。在区间 [left, right] 内，这些下标对应的的 y 值都满足条件。当 `ages[left] > 0.5 × ages[x]+7` 时，左指针停止右移。当 `ages[right+1] > ages[x]` 时， 右指针停止右移。在 `[left, right]` 区间内，满足条件的 y 有 `right-left+1` 个，即使得 `ages[y]` 取值在 `(0.5 × ages[x]+7,ages[x]]` 之间。依照题意，`x≠y`，即该区间右边界取不到。y 的取值个数需要再减一，减去的是取到和 x 相同的值的下标。那么每个区间能取 `right-left` 个值。累加所有满足条件的值即为好友请求总数。
+- 解法一。在解法二中，计算满足不等式 y 下标所在区间的时候，区间和区间存在重叠的情况，这些重叠情况导致了重复计算。所以这里可以优化。可以用 prefix sum 前缀和数组优化。代码见下方。
 
 ## 代码
 
 ```go
 package leetcocde
 
+import "sort"
+
+// 解法一 前缀和，时间复杂度 O(n)
 func numFriendRequests(ages []int) int {
+	count, prefixSum, res := make([]int, 121), make([]int, 121), 0
+	for _, age := range ages {
+		count[age]++
+	}
+	for i := 1; i < 121; i++ {
+		prefixSum[i] = prefixSum[i-1] + count[i]
+	}
+	for i := 15; i < 121; i++ {
+		if count[i] > 0 {
+			bound := i/2 + 8
+			res += count[i] * (prefixSum[i] - prefixSum[bound-1] - 1)
+		}
+	}
+	return res
+}
+
+// 解法二 双指针 + 排序，时间复杂度 O(n logn)
+func numFriendRequests1(ages []int) int {
+	sort.Ints(ages)
+	left, right, res := 0, 0, 0
+	for _, age := range ages {
+		if age < 15 {
+			continue
+		}
+		for ages[left]*2 <= age+14 {
+			left++
+		}
+		for right+1 < len(ages) && ages[right+1] <= age {
+			right++
+		}
+		res += right - left
+	}
+	return res
+}
+
+// 解法三 暴力解法 O(n^2)
+func numFriendRequests2(ages []int) int {
 	res, count := 0, [125]int{}
 	for _, x := range ages {
 		count[x]++
