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. 分析
核心思路:排序+二分查找。
排序。
固定左端点,通过二分查找,寻找满足条件 lower <= sum <= upper 的右端点上下界。
遍历每个左端点求解答案。
时间复杂度:
排序: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)
}
评论