题目描述：
给你一个下标从 0 开始、长度为 n 的整数数组 nums ，和两个整数 lower 和 upper ，返回 公平数对的数目 。
如果 (i, j) 数对满足以下情况，则认为它是一个 公平数对 ：
0 <= i < j < n，且lower <= nums[i] + nums[j] <= upper
数据范围：
$1\le nums.len \le 10^5$
题解：
排序 + 二分：
可以直接排序，对每一个 $nums[j]$ 找左边界右边界。即 $lower - nums[j] <= nums[i] <= upper - nums[j]$ 。
双指针：
将区间 $[l, r]$ 问题转化为，求小于等于 $upper$ 的对数，减去求小于等于 $lower$ 的对数。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long countFairPairs(vector<int> &nums, int lower, int upper)
{
sort(nums.begin(), nums.end());
long long ans = 0;
int n = nums.size();
for (int i = 1; i < n; ++i)
{
int index1 = upper_bound(nums.begin(), nums.begin() + i, upper - nums[i]) - nums.begin() - 1;
int index2 = lower_bound(nums.begin(), nums.begin() + i, lower - nums[i]) - nums.begin();
if (index1 >= index2)
ans += index1 - index2 + 1;
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
| auto optimize_cpp_stdio = []()
{
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
std::cout.tie(nullptr);
return 0;
}();
class Solution
{
public:
const static int maxn = 1e5 + 10;
const static int maxm = 1e5 + 10;
const int INF = 0x3f3f3f3f;
long long solve(vector<int> &nums, int upper)
{
int n = nums.size();
int l = 0, r = n - 1;
long long sum = 0;
while (l < r)
{
if (nums[l] + nums[r] > upper)
{
--r;
}
else
{
sum += r - l;
++l;
}
}
return sum;
}
long long countFairPairs(vector<int> &nums, int lower, int upper)
{
sort(nums.begin(), nums.end());
long long ans = 0;
int n = nums.size();
return solve(nums, upper) - solve(nums, lower - 1);
}
};
|