825. 适龄的朋友

Difficulty
Medium
Tags
双指针
URL
https://leetcode-cn.com/problems/friends-of-appropriate-ages/
Star
在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。
如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：
  • age[y] <= 0.5 * age[x] + 7
  • age[y] > age[x]
  • age[y] > 100 && age[x] < 100
否则，x 将会向 y 发送一条好友请求。
注意，如果 x 向 y 发送一条好友请求，y 不必也向 x 发送一条好友请求。另外，用户不会向自己发送好友请求。
返回在该社交媒体网站上产生的好友请求总数。
示例 1：
输入：ages = [16,16]
输出：2
解释：2 人互发好友请求。
示例 2：
输入：ages = [16,17,18]
输出：2
解释：产生的好友请求为 17 -> 16 ，18 -> 17 。
示例 3：
输入：ages = [20,30,100,110,120]
输出：3
解释：产生的好友请求为 110 -> 100 ，120 -> 110 ，120 -> 100 。

法1 双指针

思路
题目虽然有三个条件，但是条件3是条件2的子集，所以只需要考虑前两个条件。
综合一下前两个条件就是，满足如下条件：
用户 x就会向用户 y发送好友请求
所以就有朴素的思路：
  • 对ages进行升序排序
  • 然后向后遍历每一个age，采用双指针计算当前age可以发送人数
题解
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        n = len(ages)
        ages.sort()

        res = 0
        for i in range(len(ages)):
            age = ages[i]
            left, right = i-1, i+1
            # 只有大于等于 15 岁的才可能满足条件
            if age >= 15:
                # 向左边遍历查找满足条件的最左边的下标
                while left >=0 and ages[left] > 0.5 * age + 7:
                    left -= 1
                # 向右边遍历查找 右边只需要满足 等于即可
                while right < len(ages) and ages[right] == age:
                    right += 1
                print(i, left, right)
                res += right - left + 1 - 1 - 1 - 1

        return res

法2 优化双指针

思路
在法1的基础上，可以发现，后面age的满足区间一定在前面age满足区间的整体后面，所以双指针不必每次都从i开始。
题解
class Solution:
    def numFriendRequests(self, ages: List[int]) -> int:
        n = len(ages)
        ages.sort()
        left, right = 0, 1
        ans = 0
        # left, right 不用每次查找都从初始值开始
				# 因为后面age的区间整体上肯定是在前面区间的整体后移的
        for age in ages:
            if age < 15:
                continue
            while ages[left] <= 0.5 * age + 7:
                left += 1
            while right < n and ages[right] <= age:
                right += 1

            ans += right - left + 1 - 1 - 1
        return ans

树状数组

思路：利用给定数组构建好树状数组之后，然后不断的查询每个区间中元素的个数。
略