给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
0 <= i < j < n，且lower <= nums[i] + nums[j] <= upper
思路1：排序+二分查找
适用于离散程度较大的数据
-
class Solution { public:long long countFairPairs(vector<int>& nums, int lower, int upper) {//排序sort(nums.begin(),nums.end());//lower-nums[i]<=nums[j]<=upper-nums[i]//使用二分查找找到符合位置long long ans=0;int n=nums.size();for(int i=0;i<n;i++){auto right = upper_bound(nums.begin(), nums.begin() + i, upper - nums[i]);auto left = lower_bound(nums.begin(), nums.begin() + i, lower - nums[i]);ans += right-left;}return ans;} };思路二：哈希表+遍历
-
适用于连续性较好的数据
-
class Solution { public:long long countFairPairs(vector<int>& nums, int lower, int upper) {int n = nums.size();unordered_map<int, int> mp;long long res = 0;// 统计每个数字的出现次数for (int i = 0; i < n; i++) {mp[nums[i]]++;}// 遍历每个数字for (int i = 0; i < n; i++) {if (nums[i] > upper) {continue;}// 更新哈希表，避免重复计数mp[nums[i]]--;// 计算 j 的范围int start = max(lower - nums[i], 0);int end = upper - nums[i];// 遍历可能的 jfor (int j = start; j <= end; j++) {if (mp.find(j) != mp.end()) {res += mp[j];}}}return res;} };
