Readme

2563.Count-the-Number-of-Fair-Pairs

初看这道题的时候，一个比较自然的想法是，遍历每个j，查看j之前的有多少个符合条件的元素满足lower-nums[j] <= nums[i] <= upper-nums[j]。这就要求j之前的元素必须是有序的。但是每考察完一个j，就需要将nums[0:j]重新排序，这样的复杂度太高。

这时候我们再换一个角度。这里i与j其实是对称的。我们没有必要纠结于i<j。只要把所有满足条件的配对找出来，必然包含了所有的i<j与i>j，只要除以二就可以。所以我们只需要将nums排一次序。对于其中任意的元素x，用二分法求出有多少个符合条件的元素满足在[lower-x, pper-x]的区间范围内即可。

但是这里有个关键点，就是上述方法中，x本身可能就恰好在[lower-x, pper-x]的范围内。这样我们会误加上(x,x)这样的组合。所以我们要验证一下，如果(x,x)满足条件，就额外从计数器里减一。最终总的计数除以二，就是合法的i<j的组合。