Count the Number of Fair Pairs
Given a 0-indexed integer array nums of size n and two integers lower and upper , return the number of fair pairs.
A pair (i, j) is fair if:
- 0 <= i < j < n , and
- lower <= nums[i] + nums[j] <= upper
Example 1:
Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6 Output: 6 Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).
Example 2:
Input: nums = [1,7,9,2,5], lower = 11, upper = 11 Output: 1 Explanation: There is a single fair pair: (2,3).
Constraints:
- $1 \leq \text{nums.length} \leq {10}^{5}$
- $\text{nums.length} \ \mathrm{==} \ n$
- $-10^9 \leq \text{nums}[i] \leq 10^9$
- $-10^9 \leq \text{lower} \leq \text{upper} \leq 10^9$
解题思路
枚举$i$,然后在$0 \leq j < i$中统计有多少个$j$满足$\text{lower} - \text{nums}[i] \leq \text{nums}[j] \leq \text{upper} - \text{nums[i]}$,这个还是很容易想到的。比赛的时候没有想到简单的做法,硬是写了个离散化加树状数组过了。
AC代码如下:
1 const int N = 3e5 + 10; 2 3 int xs[N], sz; 4 int tr[N]; 5 6 int lowbit(int x) { 7 return x & -x; 8 } 9 10 void add(int x, int c) { 11 for (int i = x; i <= sz; i += lowbit(i)) { 12 tr[i] += c; 13 } 14 } 15 16 int query(int x) { 17 int ret = 0; 18 for (int i = x; i; i -= lowbit(i)) { 19 ret += tr[i]; 20 } 21 return ret; 22 } 23 24 int find(int x) { 25 int l = 1, r = sz; 26 while (l < r) { 27 int mid = l + r >> 1; 28 if (xs[mid] >= x) r = mid; 29 else l = mid + 1; 30 } 31 return l; 32 } 33 34 class Solution { 35 public: 36 long long countFairPairs(vector<int>& nums, int lower, int upper) { 37 int n = nums.size(); 38 sz = 0; 39 for (int i = 0; i < n; i++) { 40 xs[++sz] = nums[i]; 41 xs[++sz] = lower - nums[i]; 42 xs[++sz] = upper - nums[i]; 43 } 44 sort(xs + 1, xs + sz + 1); 45 sz = unique(xs + 1, xs + sz + 1) - xs - 1; 46 memset(tr, 0, sizeof(tr)); 47 long long ret = 0; 48 for (int i = 1; i < n; i++) { 49 add(find(nums[i - 1]), 1); 50 ret += query(find(upper - nums[i])) - query(find(lower - nums[i]) - 1); 51 } 52 return ret; 53 } 54 };
我一直想着这才第二题怎么会这么复杂,实际上还是有简单写法的,就是没想到。
主要是是$j < i$这个条件限制,如果没有这个限制,直接问有多少个$j$满足$\text{lower} - \text{nums}[i] \leq \text{nums}[j] \leq \text{upper} - \text{nums[i]}$,那么就可以对$\text{nums}$数组排序然后二分。而实际上是可以直接忽略这个限制来二分,最后答案除以$2$就好了。
当枚举到$i$,如果存在$j > i$并且满足上述的不等式,那么是肯定可以二分到$\text{nums}[j]$。然后当枚举到了$j$,之前的$i < j$并且满足不等式,一样可以可以二分到$\text{nums}[i]$。所以如果存在$j < i$且满足$\text{lower} \leq \text{nums[i]} + \text{nums}[j] \leq \text{upper}$,若不考虑$j < i$这个条件来二分,数对是会被累计两次,所以最后答案除以$2$就可以了。
还需要注意的是,当枚举到$i$如果有$\text{lower} \leq \text{nums[i]} \leq \text{upper}$,那么会二分到$\text{nums}[i]$,这就需要减去这个情况了。
AC代码如下:
1 class Solution { 2 public: 3 long long countFairPairs(vector<int>& nums, int lower, int upper) { 4 nums.push_back(2e9 + 1); // 加哨兵,保证可以二分到答案 5 int n = nums.size(); 6 sort(nums.begin(), nums.end()); 7 long long ret = 0; 8 function<int(int x)> find = [&](int x) { 9 int l = 0, r = n - 1; 10 while (l < r) { 11 int mid = l + r >> 1; 12 if (nums[mid] >= x) r = mid; 13 else l = mid + 1; 14 } 15 return l; 16 }; 17 for (int i = 0; i < n - 1; i++) { 18 int l = lower - nums[i], r = upper - nums[i]; 19 ret += find(r + 1) - find(l); 20 if (nums[i] >= l && nums[i] <= r) ret--; 21 } 22 return ret / 2; 23 } 24 };
参考资料
【LitteXi】统计公平数对的数目:https://leetcode.cn/problems/count-the-number-of-fair-pairs/solution/littexi-tong-ji-gong-ping-shu-dui-de-shu-n27n/
标签:Count,upper,Pairs,nums,int,text,Number,leq,lower From: https://www.cnblogs.com/onlyblues/p/17113879.html