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