题目描述
给你一个下标从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 <= 105nums.length == n-109 <= nums[i] <= 109-109 <= lower <= upper <= 109
解决方案：
算法目标
统计数组中满足以下条件的有序对(i, j)的数量：
下标满足
i < j（在原始顺序中）数值满足
lower ≤ nums[i] + nums[j] ≤ upper
核心思路
先排序数组：为使用二分查找创造条件
固定较大数j，查找较小数i：对每个位置
j，在其左侧[0, j)范围内查找满足条件的i二分查找确定范围：通过两次二分查找确定满足条件的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个有序对
算法优势
高效：O(n log n) vs 暴力O(n²)
简洁：逻辑清晰，代码简短
实用：适用于大规模数据
通用：可扩展解决类似区间和问题
函数源码：
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; } };
