难度: Medium
给你一个下标从 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,9) 。
提示：
1 <= nums.length <= 105nums.length == n-109 <= nums[i] <= 109-109 <= lower <= upper <= 109运行时间: 163 ms
内存: 29.2 MB
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums.sort()
def fn(target: int) -> int:
left, right, count = 0, len(nums) - 1, 0
while left < right:
if nums[left] + nums[right] > target:
right -= 1
else:
count += right - left
left += 1
return count
return fn(upper) - fn(lower - 1)
这个题解采用了排序加双指针的方法。首先对数组进行排序，然后使用一个辅助函数fn来计算在某个目标值target下，数组中有多少对数的和小于等于target。在fn中，使用双指针left和right分别指向数组的开头和末尾，当nums[left] + nums[right]大于target时，说明需要减小和，所以将right指针左移；否则，说明找到了right - left对数的和小于等于target，将这些对数加入到计数中，并将left指针右移。最后，返回公平数对的数目，即在upper下的数对数目减去在lower-1下的数对数目。
时间复杂度: O(n log n)
空间复杂度: O(1)
class Solution:
def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
nums.sort()
def fn(target: int) -> int:
left, right, count = 0, len(nums) - 1, 0
while left < right:
if nums[left] + nums[right] > target:
right -= 1
else:
count += right - left
left += 1
return count
return fn(upper) - fn(lower - 1)
排序加双指针方法在处理数组中的两数问题时非常有效，尤其是当问题涉及到数对和的比较时。通过排序，我们可以将复杂度较高的问题简化，因为排序后的数组可以让我们更容易地通过调整指针来控制数对的和。具体到这个问题中，使用双指针可以有效地搜索所有可能的数对组合，并快速判断它们的和是否符合条件。相比于暴力方法（O(n^2)复杂度），排序加双指针方法将时间复杂度降低到O(n log n)（排序）+ O(n)（双指针遍历），从而实现更高效的计算。此外，这种方法在实现上直观且容易理解，有助于避免复杂的哈希表或二分搜索实现，尤其是在边界条件处理上更为简洁。
在双指针算法中，通过逐步移动左指针（left）或右指针（right）来遍历所有可能的数对。当`nums[left] + nums[right]`超过目标值时，减小`right`（即减小数对的和）以搜索更小的和；当和小于等于目标值时，则所有从`left`到`right`之间的点都可以与`left`点组成合法的数对（因为数组是排序的，所以这些数对的和也一定小于等于目标值）。这时，直接计算这些数对的数量（`right - left`），然后移动`left`指针继续寻找新的可能数对。这种方法确保了每个数对只被计算一次，且没有遗漏。
这种计算方法的逻辑基于数组已经被排序的事实。当`nums[left] + nums[right]`小于等于目标值时，由于数组是升序的，因此`nums[left]`和`left`与`right`之间的任何一个元素相加也都必然小于等于目标值。所以，所有这些元素都可以与`left`形成一个有效的数对。`right - left`即为这些满足条件的数对的数量，因为它表示`left`与其右侧所有元素（不包括`right`本身）之间的距离。每次这样计算后，将`left`右移一位，是为了寻找下一个可能的组合，确保每个可能的数对都能被检查到。