comments | difficulty | edit_url | rating | source | tags | ||||
---|---|---|---|---|---|---|---|---|---|
true |
Medium |
1720 |
Weekly Contest 332 Q2 |
|
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
, andlower <= 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 <= nums.length <= 105
nums.length == n
-109 <= nums[i] <= 109
-109 <= lower <= upper <= 109
First, we sort the array nums
in ascending order. Then, for each nums[i]
, we use binary search to find the lower bound j
of nums[j]
, i.e., the first index that satisfies nums[j] >= lower - nums[i]
. Then, we use binary search again to find the lower bound k
of nums[k]
, i.e., the first index that satisfies nums[k] >= upper - nums[i] + 1
. Therefore, [j, k)
is the index range for nums[j]
that satisfies lower <= nums[i] + nums[j] <= upper
. The count of these indices corresponding to nums[j]
is k - j
, and we can add this to the answer. Note that
The time complexity is nums
.
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums.sort()
ans = 0
for i, x in enumerate(nums):
j = bisect_left(nums, lower - x, lo=i + 1)
k = bisect_left(nums, upper - x + 1, lo=i + 1)
ans += k - j
return ans
class Solution {
public long countFairPairs(int[] nums, int lower, int upper) {
Arrays.sort(nums);
long ans = 0;
int n = nums.length;
for (int i = 0; i < n; ++i) {
int j = search(nums, lower - nums[i], i + 1);
int k = search(nums, upper - nums[i] + 1, i + 1);
ans += k - j;
}
return ans;
}
private int search(int[] nums, int x, int left) {
int right = nums.length;
while (left < right) {
int mid = (left + right) >> 1;
if (nums[mid] >= x) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
class Solution {
public:
long long countFairPairs(vector<int>& nums, int lower, int upper) {
long long ans = 0;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size(); ++i) {
auto j = lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]);
auto k = lower_bound(nums.begin() + i + 1, nums.end(), upper - nums[i] + 1);
ans += k - j;
}
return ans;
}
};
func countFairPairs(nums []int, lower int, upper int) (ans int64) {
sort.Ints(nums)
for i, x := range nums {
j := sort.Search(len(nums), func(h int) bool { return h > i && nums[h] >= lower-x })
k := sort.Search(len(nums), func(h int) bool { return h > i && nums[h] >= upper-x+1 })
ans += int64(k - j)
}
return
}
function countFairPairs(nums: number[], lower: number, upper: number): number {
const search = (x: number, l: number): number => {
let r = nums.length;
while (l < r) {
const mid = (l + r) >> 1;
if (nums[mid] >= x) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
};
nums.sort((a, b) => a - b);
let ans = 0;
for (let i = 0; i < nums.length; ++i) {
const j = search(lower - nums[i], i + 1);
const k = search(upper - nums[i] + 1, i + 1);
ans += k - j;
}
return ans;
}