题目直达

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 <= 105

  • nums.length == n

  • -109 <= nums[i] <= 109

  • -109 <= lower <= upper <= 109

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)
}