@ninijia 在 Leetcode每日一题练习 ------ 2563. 统计公平数对的数目 中发帖
从Leetcode 每日一题练习继续讨论:
2563. 统计公平数对的数目
2563. Count the Number of Fair Pairs
题解
本题要找满足两个数的和在某个范围内且下标满足题目要求的组合有多少对,要找到和在某个范围内的两个数字,在知道其中一个数字的情况下即可知道另外一个数字的取值范围,若要能根据数字的取值范围确定数字在数组中的范围,则必须是有序数组,因此第一步先将数组排序。
在将数组排序后,遍历有序数组,对每个数字知道了其另一个匹配数字的左右边界,通过二分法找出满足左右边界的有序数组中的下标,再求出这个边界内的数组长度并加和到最终结果中。至于题目中的原始数组的下标条件其实对本题并没有什么影响,因为只要两个数字的和满足范围条件,则二者必有一个数字在前另一个数字在后。
代码
class Solution {
public:
long long co...