[LeetCode] 每日一题 2563. 统计公平数对的数目（二分查找 + 化简）

题目描述

给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。

如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：

• 0 <= i < j < n，且

• lower <= nums[i] + nums[j] <= upper

题目链接

https://leetcode.cn/problems/count-the-number-of-fair-pairs

示例输入

示例 1

输入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
输出：6
解释：共计 6 个公平数对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。

示例 2

输入：nums = [1,7,9,2,5], lower = 11, upper = 11
输出：1
解释：只有单个公平数对：(2,3) 。

提示

• 1 <= nums.length <= 10^5

• nums.length == n

• -109 <= nums[i] <= 10^9

• -109 <= lower <= upper <= 10^9

解题思路

这道题一开始看上去限制挺多，要求我们找出所有满足 0 <= i < j < n 且 lower <= nums[i] + nums[j] <= upper 的数对。

但其实只要认真分析一下，就会发现这题的精髓在于如何有效地统计符合某个范围的数对数量。尤其是：

• i < j 的约束并不复杂，只要我们在枚举 j 时让 i < j 就能满足；

• 重点是处理 lower <= nums[i] + nums[j] <= upper，我们可以移项整理出：

lower - nums[j] <= nums[i] <= upper - nums[j]

于是问题变成了：固定 nums[j]，统计在 [0, j-1] 区间中，有多少个 nums[i] 落在这个范围里。

这就很自然地联想到排序 + 二分查找的组合拳了：

1. 先对整个数组排序；

2. 然后从后往前枚举每个 j，每次在 [0, j) 中查找满足条件的 i 的个数；

3. 通过两次二分查找，分别定位下界和上界的索引，差值就是符合条件的配对数量。

这是一种典型的转化 + 二分查找解法，在性能和思路上都非常优雅 ✨

代码实现

class Solution {
    public long countFairPairs(int[] nums, int lower, int upper) {
        int n = nums.length;
        Arrays.sort(nums);
        long ans = 0;
        for (int j = n - 1; j >= 0; j--) {
            int left = findLower(nums, j, lower - nums[j]);
            int right = findLower(nums, j, upper - nums[j] + 1);
            ans += right - left;
        }
        return ans;
    }

    private int findLower(int[] nums, int right, int target) {
        int left = -1;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            if (nums[mid] < target) {
                left = mid;
            } else {
                right = mid;
            }
        }
        return right;
    }
}

复杂度分析

• 时间复杂度：O(n log n)

  • 排序是 O(n log n)，每个元素执行两次二分查找也是 O(log n)，总体是 O(n log n) ✅

• 空间复杂度：

  • O(1)（不考虑排序时的额外空间）或 O(n)（基于系统排序实现）🌱

虽然暴力解法是 O(n^2)，但通过转化成“查找区间内满足条件的个数”，我们用二分大幅提升效率，是一道典型的优化枚举场景题 💡

总结

这题关键在于思维上的“化简”能力。通过移项、排序、二分查找，我们把一个看似复杂的双重约束问题，转化为了经典的区间计数问题。也算是滑动窗口/双指针解法的衍生，用更精确的二分进行控制。值得收藏！🔥

希望这篇分享能为你带来启发！如果你有任何问题或建议，欢迎在评论区留言，与我共同交流探讨。