給你一個下標從 0 開始、長度為 n 的整數數組 nums ，和兩個整數 lower 和 upper ，返回 公平數對的數目 。

如果 (i, j) 數對滿足以下情況，則認為它是一個 公平數對 ：

0 <= i < j < n，且
lower <= nums[i] + nums[j] <= upper

示例 1：

輸入：nums = [0,1,7,4,4,5], lower = 3, upper = 6
輸出：6
解釋：共計 6 個公平數對：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) 。
示例 2：

輸入：nums = [1,7,9,2,5], lower = 11, upper = 11
輸出：1
解釋：只有單個公平數對：(2,3) 。

提示：

1 <= nums.length <= 10${}^5$
nums.length == n
-10${}^9$ <= nums[i] <= 10${}^9$
-10${}^9$ <= lower <= upper <= 10${}^9$

先對nums排序，然后可以用相向雙指針找出兩數之和小于等于upper的數對數，然后再用相向雙指針找出兩數之和小于lower的數對數，兩者相減即可：

class Solution {
public:long long countFairPairs(vector<int>& nums, int lower, int upper) {sort(nums.begin(), nums.end());return getNum(nums, upper) - getNum(nums, lower - 1);}long long getNum(vector<int>& nums, int target) {long long ret = 0;int left = 0;int right = nums.size() - 1;while (left < right) {if (nums[left] + nums[right] > target) {--right;// 如果兩指針指向的數之和<=target// 則[left + 1, right]之間的每個數都可以和left組成和<=target的數對} else {ret += right - left;++left;}}return ret;}
};

如果nums的長度為n，則此算法時間復雜度為O(nlogn)，瓶頸在排序處，雙指針循環的時間復雜度為O(n)；空間復雜度為O(logn)，主要是排序的棧開銷。