2563: Count-the-Number-of-Fair-Pairs
Medium
table of contents
For this question, you can simplify it to:
To accomplish this, we can create a two-pointers
function that calculates the number of pairs that are smaller
than equal to target.
In this function, we have 2 pointers; l points to the
beginning of nums, while r points to the end
of nums, and an ans variable to track the .
Now, while l < r,
code
class Solution {
public:
long long lessThanTarget(vector<int>& nums, int target) {
long long l = 0, r = nums.size()-1, ans = 0;
while (l < r) {
if (nums[l] + nums[r] <= target) {
ans += r-l;
++l;
} else {
--r;
}
}
return ans;
}
long long countFairPairs(vector<int>& nums, int lower, int upper) {
sort(nums.begin(), nums.end());
return lessThanTarget(nums, upper) - lessThanTarget(nums, lower-1);
}
};