题目直达

1. 题目描述

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

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

• 0 <= i < j < n，且

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

示例 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⁵

• nums.length == n

• -10⁹ <= nums[i] <= 10⁹

• -10⁹ <= lower <= upper <= 10⁹

2. 分析

核心思路：排序+二分查找。

1. 排序。

2. 固定左端点，通过二分查找，寻找满足条件 lower <= sum <= upper 的右端点上下界。

3. 遍历每个左端点求解答案。

时间复杂度：

• 排序：O(nlogn）

• 固定左端点扫描：O(n)，右端点上下界扫描：O(logn)。复杂度：O(nlogn)。

整体复杂度：O(nlogn)。

3. 代码

func countFairPairs(nums []int, lower int, upper int) int64 {
    sort.Ints(nums)
    fmt.Println(nums)
    n := len(nums)
    ans := 0
    // 二分查找：固定左端点，查找右端点的上下界
    for i := 0; i < n; i++ {
        low := sort.Search(n-i-1, func(idx int) bool {
            return nums[i] + nums[idx+i+1] >= lower
        })
        up := sort.Search(n-i-1, func(idx int) bool {
            return nums[i] + nums[idx+i+1] > upper
        })
        if low < up {
            ans += up-low
        }
    }
    return int64(ans)
}