逐步解析力扣825. 适龄的朋友（一题双解【排序 + 双指针】【计数排序 + 前缀和】）

逐步解析力扣825. 适龄的朋友（一题双解【排序 + 双指针】【计数排序 + 前缀和】）

https://leetcode-cn.com/problems/friends-of-appropriate-ages/

代码

public class Algr {

    public static void main(String[] args) {
        int[] a = {20,30,100,110,120};
        int[] b = {2,3,0,4,8};
        System.out.println(numFriendRequests2(a));
    }

    public static int numFriendRequests1(int[] ages) {
        int n = ages.length;
        Arrays.sort(ages);
        int left = 0,right = 0,ans = 0;
        for (int age : ages) {
            if (age<15) continue;
            while (ages[left] <= 0.5 * age + 7) ++left;
            while (right + 1 < n && ages[right + 1] <= age) ++ right;
            ans += right - left;
        }
        return ans;
    }

    public static int numFriendRequests2(int[] ages) {
        int[] cnt = new int[121];
        for (int age : ages) {
            ++cnt[age];
        }
        int[] pre = new int[121];
        for (int i = 1; i <= 120; ++i) {
            pre[i] = pre[i - 1] + cnt[i];
        }
        int ans = 0;
        for (int i = 15; i <= 120; ++i) {
            if (cnt[i] > 0) {
                int bound = (int) (i * 0.5 + 8);
                ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
            }
        }
        return ans;
    }

}

方法一：排序 + 双指针

先排序，升序后，初始化左右指针和基本值

int n = ages.length;
Arrays.sort(ages);
int left = 0,right = 0,ans = 0;

之后开始遍历

for (int age : ages) {
   if (age<15) continue;
       while (ages[left] <= 0.5 * age + 7) ++left;
       while (right + 1 < n && ages[right + 1] <= age) ++ right;
        ans += right - left;
}

循环里干了三件事，小于15直接走下次，左和右指针的遍历，画图理解

计算结果一样

方法二：计数排序 + 前缀和

一共三步，初始化cnt数组，初始化pre数组，遍历算值

1.cnt数组的作用给有age的数组标记为1

int[] cnt = new int[121];
for (int age : ages) {
    ++cnt[age];
}

2.pre数组的作用就是将标记的age进行累加，20到30这里从1变成2

int[] pre = new int[121];
for (int i = 1; i <= 120; ++i) {
   pre[i] = pre[i - 1] + cnt[i];
}

3.最后一步，先算出边界int bound = (int) (i * 0.5 + 8); 主值和边界值相减-1，累加到最终结果ans上

int ans = 0;
for (int i = 15; i <= 120; ++i) {
     if (cnt[i] > 0) {
         int bound = (int) (i * 0.5 + 8);
         ans += cnt[i] * (pre[i] - pre[bound - 1] - 1);
     }
}
return ans;