day120—二分查找—统计公平数对的数目（LeetCode-2563）

题目描述

给你一个下标从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

解决方案：

算法目标

统计数组中满足以下条件的有序对(i, j)的数量：

1. 下标满足i < j（在原始顺序中）

2. 数值满足lower ≤ nums[i] + nums[j] ≤ upper

核心思路

1. 先排序数组：为使用二分查找创造条件

2. 固定较大数j，查找较小数i：对每个位置j，在其左侧[0, j)范围内查找满足条件的i

3. 二分查找确定范围：通过两次二分查找确定满足条件的i的范围

算法步骤详解

1. 预处理：排序

sort(nums.begin(), nums.end());

• 将数组变为有序，便于二分查找

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

2. 自定义二分查找函数

int lower_bound(vector<int>& nums, int start, int end, int target)

• 在nums[start..end)范围内查找第一个 ≥ target的元素位置

• 使用(left=start-1, right=end)的开区间写法

• 循环条件：left+1 < right，确保区间不断缩小

• 返回right，即第一个≥target的位置

3. 主逻辑

对每个元素nums[i]（将其视为j）：

int l = lower_bound(nums, 0, i, lower - nums[i]); int r = lower_bound(nums, 0, i, upper - nums[i] + 1); ans += r - l;

• 转换条件：lower ≤ nums[i] + nums[j] ≤ upper

  等价于lower - nums[j] ≤ nums[i] ≤ upper - nums[j]

• 查找左边界l：第一个≥ lower-nums[j]的位置

• 查找右边界r：第一个≥ upper-nums[j]+1的位置

  • 这等价于第一个> upper-nums[j]的位置

• 统计个数：满足条件的i在区间[l, r)，个数为r-l

关键特性

• 确保i<j：只在[0, j)范围内查找

• 避免重复：每个有序对(i, j)只被统计一次

• 处理边界：使用upper-nums[i]+1模拟upper_bound

时间复杂度

• 排序：O(n log n)

• 对每个元素两次二分查找：n × 2 × O(log n) = O(n log n)

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

空间复杂度

• O(1) 或 O(n)（取决于排序算法）

示例说明

nums = [0,1,7,4,4,5] lower = 3, upper = 6 排序后: [0,1,4,4,5,7] j=2 (值4): 在[0,2)中找满足3-4≤x≤6-4即[-1,2]的数 → 找到0,1 → 2个 j=3 (值4): 同样找到2个 j=4 (值5): 在[0,4)中找[-2,1] → 找到0,1 → 2个 总计: 6个有序对

算法优势

1. 高效：O(n log n) vs 暴力O(n²)

2. 简洁：逻辑清晰，代码简短

3. 实用：适用于大规模数据

4. 通用：可扩展解决类似区间和问题

函数源码：

class Solution { public: int lower_bound(vector<int>&nums,int start,int end,int target){ int left=start-1; int right=end; while(left+1<right){ int mid=(left+right)/2; if(nums[mid]<target) left=mid; else right=mid; } return right; } long long countFairPairs(vector<int>& nums, int lower, int upper) { sort(nums.begin(),nums.end()); int len=nums.size(); long long ans=0; for(int i=0;i<len;i++){ int l=lower_bound(nums,0,i,lower-nums[i]); int r=lower_bound(nums,0,i,upper-nums[i]+1); ans += r-l; } return ans; } };