题目描述

825. 适龄的朋友

题解

根据题目的约束的出 0.5x+7 <= y <= x ，对于y来说需要寻找符合的范围边界。参考下图：

因为随着age[x]增长，则age[y]的边界也会基于前面的基础上向右扩张，所以我们可以先加age排序，则通过age查找边界的时间复杂度为O(n)
每一个age[x]的贡献是边界内的元素个数，因此遍历数组ages，不断移动左右边界指针，找到满足条件的区间，算出每个区间的贡献。

代码参考：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {

        //   age[y] <= 0.5 * age[x] + 7
        //   age[y] > age[x]
        //   age[y] > 100 && age[x] < 100

        //   y<= x <= 2y -14
        public int numFriendRequests(int[] ages) {
            if (ages == null || ages.length <= 1) {
                return 0;
            }
            int n = ages.length;
            Arrays.sort(ages);
            int left = 0;
            int right = 0;
            int res = 0;
            for (int i = 0; i < n; i++) {
                int age = ages[i];
                //y<= x <= 2y -14 // 左边边界扩充 ,因y>=14 且 x>y，则age>=14
                if (age < 15) {
                    continue;
                }
                while (ages[left] <= 0.5 * age + 7) {
                    left++;
                }
                //右侧边界扩充
                while (right + 1 < n && ages[right + 1] <= age) {
                    right++;
                }
                //因排序，当age往后移，则age越大，则边界也是在当前的基础上扩充。
                //所以虽然两层循环依然时间是o(n)
                res += right - left;
            }
            return res ;
        }
    }