标签： 滑动窗口

3305.元音辅音字符串计数I

目标

给你一个字符串 word 和一个 非负 整数 k。

返回 word 的 子字符串 中，每个元音字母（'a'、'e'、'i'、'o'、'u'）至少 出现一次，并且 恰好 包含 k 个辅音字母的子字符串的总数。

示例 1：

输入：word = "aeioqq", k = 1
输出：0
解释：
不存在包含所有元音字母的子字符串。

示例 2：

输入：word = "aeiou", k = 0
输出：1
解释：
唯一一个包含所有元音字母且不含辅音字母的子字符串是 word[0..4]，即 "aeiou"。

示例 3：

输入：word = "ieaouqqieaouqq", k = 1
输出：3
解释：
包含所有元音字母并且恰好含有一个辅音字母的子字符串有：
word[0..5]，即 "ieaouq"。
word[6..11]，即 "qieaou"。
word[7..12]，即 "ieaouq"。

说明：

  • 5 <= word.length <= 250
  • word 仅由小写英文字母组成。
  • 0 <= k <= word.length - 5

思路

求给定字符串 word 的子字符串中至少包含 5 个元音且恰好包含 k 个辅音的子字符串个数。

暴力枚举子数组。

代码


/**
 * @date 2025-03-12 8:42
 */
public class CountOfSubstrings3305 {

    public int countOfSubstrings(String word, int k) {
        int n = word.length();
        Set<Character> vowel = new HashSet<>();
        Collections.addAll(vowel, 'a', 'e', 'i', 'o', 'u');
        Map<Character, Integer> map = new HashMap<>();
        int consonantCnt = 0;
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                char c = word.charAt(j);
                if (vowel.contains(c)) {
                    Integer cnt = map.getOrDefault(c, 0);
                    map.put(c, cnt + 1);
                } else {
                    consonantCnt++;
                }
                if (consonantCnt == k && map.size() == 5) {
                    res++;
                } else if (consonantCnt > k) {
                    break;
                }
            }
            map.clear();
            consonantCnt = 0;
        }
        return res;
    }

}

性能

1287.有序数组中出现次数超过25%的元素

目标

给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。

请你找到并返回这个整数

示例：

输入：arr = [1,2,2,6,6,6,6,7,10]
输出：6

说明：

  • 1 <= arr.length <= 10^4
  • 0 <= arr[i] <= 10^5

思路

有一个非递减有序整数数组，数组中恰好有一个整数出现次数大于元素总数的 25%，返回这个整数。

检查长度为 n / 4 + 1 的窗口首尾元素是否相等即可。

代码


/**
 * @date 2025-02-17 8:41
 */
public class FindSpecialInteger1287 {

    public int findSpecialInteger_v1(int[] arr) {
        int n = arr.length;
        int left = 0, right = n / 4;
        while (right < n) {
            if (arr[right] == arr[left]) {
                return arr[left];
            }
            left++;
            right++;
        }
        return -1;
    }

}

性能

219.存在重复元素II

目标

给你一个整数数组 nums 和一个整数 k ，判断数组中是否存在两个 不同的索引 i 和 j ，满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在，返回 true ；否则，返回 false 。

示例 1：

输入：nums = [1,2,3,1], k = 3
输出：true

示例 2：

输入：nums = [1,0,1,1], k = 1
输出：true

示例 3：

输入：nums = [1,2,3,1,2,3], k = 2
输出：false

说明：

  • 1 <= nums.length <= 10^5
  • -10^9 <= nums[i] <= 10^9
  • 0 <= k <= 10^5

思路

判断下标距离小于等于 k 的窗口内是否存在重复元素，窗口内的元素个数为 k + 1。

代码


/**
 * @date 2024-07-04 22:36
 */
public class ContainsNearbyDuplicate219 {

    public boolean containsNearbyDuplicate(int[] nums, int k) {
        int n = nums.length;
        Set<Integer> set = new HashSet<>(k);
        int left = 0;
        for (int right = 0; right < n; right++) {
            if (!set.add(nums[right])) {
                return true;
            }
            if (right - left == k) {
                set.remove(nums[left++]);
            }
        }
        return false;
    }

}

性能

2944.购买水果需要的最少金币数

目标

给你一个 下标从 1 开始的 整数数组 prices ，其中 prices[i] 表示你购买第 i 个水果需要花费的金币数目。

水果超市有如下促销活动：

  • 如果你花费 prices[i] 购买了下标为 i 的水果，那么你可以免费获得下标范围在 [i + 1, i + i + 1] 的水果。

注意 ，即使你 可以 免费获得水果 j ，你仍然可以花费 prices[j] 个金币去购买它以获得它的奖励。

请你返回获得所有水果所需要的 最少 金币数。

示例 1：

输入：prices = [3,1,2]
输出：4
解释：
用 prices[0] = 3 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
用 prices[1] = 1 个金币购买第 2 个水果，你可以免费获得第 3 个水果。
免费获得第 3 个水果。
请注意，即使您可以免费获得第 2 个水果作为购买第 1 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

示例 2：

输入：prices = [1,10,1,1]
输出：2
解释：
用 prices[0] = 1 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 1 个金币购买第 3 个水果，你可以免费获得第 4 个水果。
免费获得第 4 个水果。

示例 3：

输入：prices = [26,18,6,12,49,7,45,45]
输出：39
解释：
用 prices[0] = 26 个金币购买第 1 个水果，你可以免费获得第 2 个水果。
免费获得第 2 个水果。
用 prices[2] = 6 个金币购买第 3 个水果，你可以免费获得第 4，5，6（接下来的三个）水果。
免费获得第 4 个水果。
免费获得第 5 个水果。
用 prices[5] = 7 个金币购买第 6 个水果，你可以免费获得第 7 和 第 8 个水果。
免费获得第 7 个水果。
免费获得第 8 个水果。
请注意，即使您可以免费获得第 6 个水果作为购买第 3 个水果的奖励，但您购买它是为了获得其奖励，这是更优化的。

说明：

1 <= prices.length <= 1000
1 <= prices[i] <= 10^5

思路

有 n 个水果，其价格由 prices 表示，当我们以 prices[i] 枚金币购买了第 i + 1 个苹果时，我们可以免费获得下标 [i + 1, i + i + 1] 的 所有 个苹果（当然也可以购买以获得后面的奖励），求获得全部苹果所需的最少硬币。

最直接的想法是记忆化搜索。

代码


/**
 * @date 2025-01-24 9:07
 */
public class MinimumCoins2944 {

    public int minimumCoins(int[] prices) {
        int[] mem = new int[2 * prices.length + 3];
        Arrays.fill(mem, Integer.MAX_VALUE);
        return dfs(0, prices, mem, 0);
    }

    public int dfs(int index, int[] prices, int[] mem, int cost) {
        int n = prices.length;
        if (index >= n) {
            return cost;
        }
        int res = cost + prices[index];
        int next = index * 2 + 2;
        if (mem[next] == Integer.MAX_VALUE) {
            mem[next] = dfs(next, prices, mem, 0);
        }
        int remainder = mem[next];
        if (remainder == 0) {
            return res;
        }
        for (int i = index + 1; i < n && i <= index * 2 + 1; i++) {
            if (mem[i] == Integer.MAX_VALUE) {
                mem[i] = dfs(i, prices, mem, 0);
            }
            remainder = Math.min(mem[i], remainder);
        }
        return res + remainder;
    }

}

性能

3097.或值至少为K的最短子数组II

目标

给你一个 非负 整数数组 nums 和一个整数 k 。

如果一个数组中所有元素的按位或运算 OR 的值 至少 为 k ，那么我们称这个数组是 特别的 。

请你返回 nums 中 最短特别非空 子数组 的长度，如果特别子数组不存在，那么返回 -1 。

示例 1：

输入：nums = [1,2,3], k = 2
输出：1
解释：
子数组 [3] 的按位 OR 值为 3 ，所以我们返回 1 。

示例 2：

输入：nums = [2,1,8], k = 10
输出：3
解释：
子数组 [2,1,8] 的按位 OR 值为 11 ，所以我们返回 3 。

示例 3：

输入：nums = [1,2], k = 0
输出：1
解释：
子数组 [1] 的按位 OR 值为 1 ，所以我们返回 1 。

说明：

  • 1 <= nums.length <= 2 * 10^5
  • 0 <= nums[i] <= 10^9
  • 0 <= k <= 10^9

思路

求数组 nums 的最短特别子数组长度，特别子数组的所有元素按位与的结果大于等于 k。

与 3095.或值至少K的最短子数组I 相比数据范围变大了，O(n^2) 的解法会超时。

记录每一位的出现次数，使用滑动窗口，枚举右收缩左。由于 按位或 没有逆运算，我们可以反向重新计算 按位与。

代码


/**
 * @date 2025-01-17 8:40
 */
public class MinimumSubarrayLength3097 {

    public int minimumSubarrayLength_v2(int[] nums, int k) {
        int res = Integer.MAX_VALUE;
        int right = 0;
        int n = nums.length;
        int or = 0;
        while (right < n) {
            do {
                or |= nums[right++];
            } while (right < n && or < k);
            if (or >= k) {
                int left = right - 1;
                int tmp = 0;
                while (left >= 0) {
                    tmp |= nums[left--];
                    if (tmp >= k) {
                        left++;
                        break;
                    } else {
                        or = tmp;
                    }
                }
                res = Math.min(res, right - left);
            } else {
                break;
            }
        }
        return res == Integer.MAX_VALUE ? -1 : res;
    }

}

性能

3298.统计重新排列后包含另一个字符串的子字符串数目II

目标

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀，那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

注意 ，这个问题中的内存限制比其他题目要 小 ，所以你 必须 实现一个线性复杂度的解法。

示例 1：

输入：word1 = "bcca", word2 = "abc"
输出：1
解释：
唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。

示例 2：

输入：word1 = "abcabc", word2 = "abc"
输出：10
解释：
除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3：

输入：word1 = "abcabc", word2 = "aaabc"
输出：0

说明：

  • 1 <= word1.length <= 10^6
  • 1 <= word2.length <= 10^4
  • word1 和 word2 都只包含小写英文字母。

思路

参考 3297.统计重新排列后包含另一个字符串的子字符串数目I，本题内存限制小，必须使用线性复杂度的解法。

代码


/**
 * @date 2025-01-09 14:28
 */
public class ValidSubstringCount3297 {

    public long validSubstringCount_v1(String word1, String word2) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (char c : chars1) {
            cnt1[c - 'a']++;
        }
        for (char c : chars2) {
            cnt2[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] < cnt2[i]) {
                return 0;
            }
        }
        int n = word1.length();
        int r = n - 1;
        while (--cnt1[chars1[r] - 'a'] >= cnt2[chars1[r] - 'a']) {
            r--;
        }
        long res = n - r;
        cnt1[chars1[r++] - 'a']++;
        for (int i = 0; i < n - word2.length(); i++) {
            int c = chars1[i] - 'a';
            cnt1[c]--;
            while (r < n && cnt1[c] < cnt2[c]) {
                cnt1[chars1[r++] - 'a']++;
            }
            if (cnt1[c] >= cnt2[c]) {
                res += n - r + 1;
            } else {
                break;
            }
        }
        return res;
    }

}

性能

3297.统计重新排列后包含另一个字符串的子字符串数目I

目标

给你两个字符串 word1 和 word2 。

如果一个字符串 x 重新排列后，word2 是重排字符串的 前缀，那么我们称字符串 x 是 合法的 。

请你返回 word1 中 合法 子字符串 的数目。

示例 1：

输入：word1 = "bcca", word2 = "abc"
输出：1
解释：
唯一合法的子字符串是 "bcca" ，可以重新排列得到 "abcc" ，"abc" 是它的前缀。

示例 2：

输入：word1 = "abcabc", word2 = "abc"
输出：10
解释：
除了长度为 1 和 2 的所有子字符串都是合法的。

示例 3：

输入：word1 = "abcabc", word2 = "aaabc"
输出：0

说明：

  • 1 <= word1.length <= 10^5
  • 1 <= word2.length <= 10^4
  • word1 和 word2 都只包含小写英文字母。

思路

有两个字符串 word1 和 word2，求 word1 有多个子字符串 满足子串的每个字符的出现次数 均大于等于 word2 中对应字符的出现次数。

暴力解法是枚举 word1 的每个子字符串，比较子串中的每个字符个数。具体来说就是统计 word1 与 word2 中各字符的个数，枚举 word1 起点，从后向前枚举终点，如果某字符个数小于 word2 相应字符的个数则停止计数，继续下一个起点。这种解法的时间复杂度是 O(n^2) 会超时。

考虑使用滑动窗口，当左边元素移出窗口时，向右扩展，直到移出的元素个数达到 word2 中对应字符的个数，累加右边界到结尾的字符个数。

代码


/**
 * @date 2025-01-09 14:28
 */
public class ValidSubstringCount3297 {

    public long validSubstringCount_v1(String word1, String word2) {
        int[] cnt1 = new int[26];
        int[] cnt2 = new int[26];
        char[] chars1 = word1.toCharArray();
        char[] chars2 = word2.toCharArray();
        for (char c : chars1) {
            cnt1[c - 'a']++;
        }
        for (char c : chars2) {
            cnt2[c - 'a']++;
        }
        for (int i = 0; i < 26; i++) {
            if (cnt1[i] < cnt2[i]) {
                return 0;
            }
        }
        int n = word1.length();
        int r = n - 1;
        while (--cnt1[chars1[r] - 'a'] >= cnt2[chars1[r] - 'a']) {
            r--;
        }
        long res = n - r;
        cnt1[chars1[r++] - 'a']++;
        for (int i = 0; i < n - word2.length(); i++) {
            int c = chars1[i] - 'a';
            cnt1[c]--;
            while (r < n && cnt1[c] < cnt2[c]) {
                cnt1[chars1[r++] - 'a']++;
            }
            if (cnt1[c] >= cnt2[c]) {
                res += n - r + 1;
            } else {
                break;
            }
        }
        return res;
    }

}

性能

3208.交替组II

目标

给你一个整数数组 colors 和一个整数 k ，colors表示一个由红色和蓝色瓷砖组成的环，第 i 块瓷砖的颜色为 colors[i] ：

  • colors[i] == 0 表示第 i 块瓷砖的颜色是 红色 。
  • colors[i] == 1 表示第 i 块瓷砖的颜色是 蓝色 。

环中连续 k 块瓷砖的颜色如果是 交替 颜色（也就是说除了第一块和最后一块瓷砖以外，中间瓷砖的颜色与它 左边 和 右边 的颜色都不同），那么它被称为一个 交替 组。

请你返回 交替 组的数目。

注意 ，由于 colors 表示一个 环 ，第一块 瓷砖和 最后一块 瓷砖是相邻的。

示例 1：

输入：colors = [0,1,0,1,0], k = 3
输出：3

解释：

交替组包括：

示例 2：

输入：colors = [0,1,0,0,1,0,1], k = 6
输出：2

解释：

交替组包括：

示例 3：

输入：colors = [1,1,0,1], k = 4
输出：0

解释：

说明：

  • 3 <= colors.length <= 10^5
  • 0 <= colors[i] <= 1
  • 3 <= k <= colors.length

思路

有一个环形二进制数组（认为首尾相邻），如果连续的 k 个元素除了第一个与最后一个元素外，内部元素与它左边和右边的元素不同，则称这 k 个元素为一个交替组，求交替组的个数。

如果 k 取 3 就变成了 3206.交替组I。

昨天的题枚举的是中间元素，今天这道题我们可以枚举左端点。将其视为一个特殊的滑动窗口问题，特殊之处在于窗口内元素需要满足的条件是 不存在连续相等的元素。显然，如果新移入窗口的元素使得条件不满足，即窗口内后两个元素相等，那么只要窗口内包含这个新移入的元素 条件就总是无法满足。

因此可以直接将左端点移到右边界，省去了移出元素的滑动过程。在向右扩展的时候可以对窗口内的元素计数，如果大于等于 k 则计入结果，直到右端点无法再继续扩展，重置计数器，然后以右边界为左端点继续该过程。

可以省略维护左边界的指针，重置计数器就相当于从当前位置重新计数。

我们可以通过偏移下标然后取余来处理环形数组的遍历。也可以参考 134.加油站 两次循环。

代码


/**
 * @date 2024-11-26 9:31
 */
public class NumberOfAlternatingGroups3208 {

    /**
     * 两次循环1ms
     */
    public int numberOfAlternatingGroups_v2(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        int prev = colors[n - k + 1];
        int size = 1;
        for (int i = n - k + 2; i < n; i++) {
            if (colors[i] == prev) {
                size = 1;
            } else {
                size++;
            }
            prev = colors[i];
        }
        for (int i = 0; i < n; i++) {
            if (colors[i] == prev) {
                size = 1;
            } else {
                size++;
            }
            prev = colors[i];
            if (size >= k) {
                res++;
            }
        }
        return res;
    }

    /**
     * 5ms
     */
    public int numberOfAlternatingGroups_v1(int[] colors, int k) {
        int res = 0;
        int n = colors.length;
        int size = 1;
        for (int i = n - k + 2; i < 2 * n; i++) {
            if (colors[i % n] == colors[(i - 1) % n]) {
                size = 1;
            } else {
                size++;
            }
            if (size >= k) {
                res++;
            }
        }
        return res;
    }

}

性能

632.最小区间

目标

你有 k 个 非递减排列 的整数列表。找到一个 最小 区间，使得 k 个列表中的每个列表至少有一个数包含在其中。

我们定义如果 b-a < d-c 或者在 b-a == d-c 时 a < c，则区间 [a,b] 比 [c,d] 小。

示例 1：

输入：nums = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]]
输出：[20,24]
解释： 
列表 1：[4, 10, 15, 24, 26]，24 在区间 [20,24] 中。
列表 2：[0, 9, 12, 20]，20 在区间 [20,24] 中。
列表 3：[5, 18, 22, 30]，22 在区间 [20,24] 中。

示例 2：

输入：nums = [[1,2,3],[1,2,3],[1,2,3]]
输出：[1,1]

说明：

  • nums.length == k
  • 1 <= k <= 3500
  • 1 <= nums[i].length <= 50
  • -10^5 <= nums[i][j] <= 10^5
  • nums[i] 按非递减顺序排列

思路

有 k 个非递减排列的整数列表，找一个最小区间，使得 k 个列表中每个列表至少有一个元素包含其中。所谓最小区间指区间长度最小，如果长度相同，则起点小的区间更小。

可以将元素标记属于哪个列表，然后从小到大排序，使用滑动窗口，找到最小的窗口。

当元素移入/移出窗口，如何判断是否应该从集合中增加/删除列表种类？

  • 可以记录每个列表元素的最大下标，如果移出的元素等于该下标则说明窗口内不包含该列表中的元素。元素移入窗口时可以根据最大下标是否小于左边界来判断是否应该增加列表种类，考虑到开始时左边界为 0，应该将数组初始化为 -1。
  • 也可以记录每个列表在窗口元素的个数，如果从 0 变为 1 则增加种类，如果从 1 变为 0 则减少。

代码


/**
 * @date 2024-11-24 15:14
 */
public class SmallestRange632 {

    /**
     * 优化代码逻辑
     */
    public int[] smallestRange_v1(List<List<Integer>> nums) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (Integer num : nums.get(i)) {
                list.add(new int[]{num, i});
            }
        }
        int[] res = new int[]{0, 1000000};
        list.sort((a, b) -> a[0] - b[0]);
        int n = list.size(), k = nums.size();
        int l = 0;
        int[] typeMaxIndex = new int[k];
        Arrays.fill(typeMaxIndex, -1);
        int types = 0;
        for (int r = 0; r < n; r++) {
            int[] e = list.get(r);
            int right = e[0];
            int type = e[1];
            int lastTypeMaxIndex = typeMaxIndex[type];
            typeMaxIndex[type] = r;
            if (lastTypeMaxIndex < l){
                types++;
            }
            while (types == k) {
                int[] left = list.get(l);
                int lType = left[1];
                if (typeMaxIndex[lType] == l++) {
                    types--;
                    if (right - left[0] < res[1] - res[0]) {
                        res[0] = left[0];
                        res[1] = right;
                    }
                }
            }
        }
        return res;
    }

    public int[] smallestRange(List<List<Integer>> nums) {
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < nums.size(); i++) {
            for (Integer num : nums.get(i)) {
                list.add(new int[]{num, i});
            }
        }
        int[] res = new int[]{0, 1000000};
        list.sort((a, b) -> a[0] - b[0]);
        int n = list.size(), k = nums.size();
        int l = 0;
        int[] typeMaxIndex = new int[k];
        Set<Integer> set = new HashSet<>();
        for (int r = 0; r < n; r++) {
            int[] e = list.get(r);
            int right = e[0];
            int type = e[1];
            typeMaxIndex[type] = r;
            set.add(type);
            while (set.size() == k) {
                int[] left = list.get(l);
                int lType = left[1];
                if (typeMaxIndex[lType] == l++) {
                    set.remove(lType);
                }
            }
            if (l >= 1 && !set.contains(list.get(l - 1)[1]) && set.size() == k - 1) {
                int left = list.get(l - 1)[0];
                if (right - left < res[1] - res[0]) {
                    res[0] = left;
                    res[1] = right;
                }
            }
        }
        return res;
    }
}

性能

825.适龄的朋友

目标

在社交媒体网站上有 n 个用户。给你一个整数数组 ages ，其中 ages[i] 是第 i 个用户的年龄。

如果下述任意一个条件为真，那么用户 x 将不会向用户 y（x != y）发送好友请求：

  • ages[y] <= 0.5 * ages[x] + 7
  • ages[y] > ages[x]
  • ages[y] > 100 && ages[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 。

说明：

  • n == ages.length
  • 1 <= n <= 2 * 10^4
  • 1 <= ages[i] <= 120

思路

某社交网站上有 n 个用户，ages[i] 表示用户 i 的年龄，当满足条件 ages[x] >= ages[y] && ages[y] > ages[x] / 2 + 7 时，用户 x 会向 y 发送好友申请。求网站上好友申请的总数。

第三个条件 ages[y] > 100 && ages[x] < 100 即 ages[y] > 100 > ages[x] 与第二个条件重复了，可以不考虑。

ages[x] >= ages[y] > ages[x] / 2 + 7 可以推出 ages[x] > 14 才可以发出好友申请，并且好友申请的对象也要满足 ages[y] > ages[x] / 2 + 7 > 14，

将年龄从大到小排序后，使用滑动窗口计算即可。

瓶颈在于排序，可以使用计数排序。

代码


/**
 * @date 2024-11-17 14:46
 */
public class NumFriendRequests825 {

    public int numFriendRequests_v1(int[] ages) {
        int n = ages.length;
        int[] ageCnt = new int[121];
        for (int i = 0; i < n; i++) {
            ageCnt[ages[i]]++;
        }
        int res = 0, windowCnt = 0;
        int l = 15;
        for (int i = 15; i < 121; i++) {
            windowCnt += ageCnt[i];
            if (l * 2 - 14 <= i) {
                windowCnt -= ageCnt[l++];
            }
            if (windowCnt > 0) {
                res += ageCnt[i] * (windowCnt - 1);
            }
        }
        return res;
    }

    public int numFriendRequests(int[] ages) {
        Arrays.sort(ages);
        int n = ages.length;
        int r = n - 1, lowerBounds = ages[r] / 2 + 7;
        int res = 0;
        for (int l = n - 1; l >= 0 && ages[l] > 14; l--) {
            while (ages[l] <= lowerBounds) {
                lowerBounds = ages[--r] / 2 + 7;
            }
            res += r - l;
            int e = l;
            while (e < n - 1 && ages[e] == ages[e + 1]) {
                res++;
                e++;
            }
        }
        return res;
    }
}

性能