LeetCode每日一题4.19
2563. 统计公平数对的数目
题目
问题分析
输入：一个整数数组 nums 和两个整数 lower 和 upper。
输出：返回满足条件的公平数对的数目，即对于所有 0 <= i < j < n，lower <= nums[i] + nums[j] <= upper 的数对 (i, j) 的数量。
思路
方法一：暴力解法（时间复杂度 O(n^2)）
直接遍历所有可能的数对 (i, j) 并检查它们是否满足条件。
方法二：优化解法（二分查找）
排序：首先对数组 nums 进行排序。
遍历：然后对每个 nums[i]，使用 二分查找 来找到满足条件的 nums[j]（其中 j > i）的范围。
二分查找：分别找到满足 nums[i] + nums[j] <= upper 的最大 j（通过 find_upper_bound）和满足 nums[i] + nums[j] >= lower 的最小 j（通过 find_lower_bound）。
代码
class Solution:def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:# 对数组进行排序nums.sort()count = 0n = len(nums)for i in range(n):# 找到满足 nums[i] + nums[j] <= upper 的最大 j 的位置r = self.find_upper_bound(nums, upper - nums[i], i + 1, n - 1)# 找到满足 nums[i] + nums[j] >= lower 的最小 j 的位置l = self.find_lower_bound(nums, lower - nums[i], i + 1, n - 1)# 统计符合条件的数对数量if l <= r:count += r - l + 1return countdef find_upper_bound(self, nums, target, start, end):while start <= end:mid = (start + end) // 2if nums[mid] > target:end = mid - 1else:start = mid + 1return enddef find_lower_bound(self, nums, target, start, end):while start <= end:mid = (start + end) // 2if nums[mid] < target:start = mid + 1else:end = mid - 1return start复杂度分析
时间复杂度：
排序：(O(n \log n))
遍历并二分查找：(O(n \log n))
因此，最终时间复杂度为：
[ O(n \log n) + O(n \log n) = O(n \log n) ]
空间复杂度：
遍历：(O(n))
学习
排序
排序是为了后续能够利用 二分查找 来高效地找到满足条件的 nums[j]。
遍历
for i in range(n):r = self.find_upper_bound(nums, upper - nums[i], i + 1, n - 1)l = self.find_lower_bound(nums, lower - nums[i], i + 1, n - 1)if l <= r:count += r - l + 1遍历每个 nums[i]：对于每个 nums[i]，我们需要找到所有 j > i 且满足 lower <= nums[i] + nums[j] <= upper 的 nums[j]。
找到 r 和 l：
r 是满足 nums[i] + nums[j] <= upper 的最大 j 的位置。
l 是满足 nums[i] + nums[j] >= lower 的最小 j 的位置。
统计数对：如果 l <= r，则 l 到 r 之间的所有 j 都是符合条件的，因此数对数量为 r - l + 1。
二分查找
find_upper_bound：找到第一个大于 target 的元素的位置（返回该位置的前一个位置）。
def find_upper_bound(self, nums, target, start, end):while start <= end:mid = (start + end) // 2if nums[mid] > target:end = mid - 1else:start = mid + 1return endfind_lower_bound：找到第一个不小于 target 的元素的位置。
def find_lower_bound(self, nums, target, start, end):while start <= end:mid = (start + end) // 2if nums[mid] < target:start = mid + 1else:end = mid - 1return start与相向双指针方法的区别
相向双指针方法 的典型特点是：
两个指针从两端向中间移动：一个指针从数组的起始位置开始（left），另一个指针从数组的末尾位置开始（right）。
根据当前 nums[left] + nums[right] 的值来决定移动哪个指针：
如果当前和小于 lower，则 left 指针右移。
如果当前和大于 upper，则 right 指针左移。
如果当前和在 [lower, upper] 范围内，则统计符合条件的数对并调整指针。