力扣每日一题之适龄的朋友

发表于

在社交媒体网站上有 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

方法一：排序+双指针

观察题目中给出的三个条件：

可知条件3是蕴含条件2中的，即如果满足条件3那么也就满足条件2。因此当条件12均不满足时，用户x就会向用户y发送好友请求。

用户y需要满足： \[ 0.5 \times ages[x]+7 < ages[y] \leq age[x] \] 当\(age[x] \leq 14\)时，不存在满足要求的ages[y]，因此我们只需要考虑\(ages[y] \geq 15\)的情况，此时满足要求的\(ages[y]\)的范围：\((0.5 \times ages[x]+7, age[x]]\)。

当\(age[x]\)增加时，上述区间的左右边界均单调递增，因此如果我们将数组的\(ages\)进行升序排序，那么就可以在遍历\(ages[x]\)的同时，使用两个指针left和right维护满足要求的左右边界。当x向后移动一个位置时：

  • 如果左边界指针left指向的元素不满足\(ages[left] > 0.5 \ times ages[x] + 7\)，那么就将左边界向右移动一个位置；
  • 如果右边界指针right指向的下一个元素满足\(ages[right+1] \geq ages[x]\)，那么就将右边界向右移动一个位置；

这样一来，\([left, right]\)就是满足要求的y的下标。需要注意的是，\(x\)本身一定在\([left, right]\)区间内，因此\(x\)发送的好友请求数，即为\([left, right]\)区间的长度-1.

我们将每一个x对应的\([left, right]\)区间的长度减去1进行累加，就可以得到最后的答案。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func numFriendRequests(ages []int) (ans int) {
        sort.Ints(ages)
        left, right := 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 ++
            }
            ans += right - left
        }
        return
    }