点击获取AI摘要

2563. 统计公平数对的数目 M

给你一个下标从 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 <= 10510^5
  • nums.length == n
  • −109-10^9 <= nums[i] <= 10910^9
  • −109-10^9 <= lower <= upper <= 10910^9

问题分析

问题本质上是寻找满足特定条件的数对 (i,j)(i, j)，其中 ii 和 jj 是数组的索引，且它们的和在给定的范围 [lower, upper] 内。这是一个典型的双指针或者排序后使用二分查找的问题，通过排序将问题转化为在有序数组中快速定位满足和的区间的边界。

算法思路

  1. 排序数组：将输入的nums数组进行升序排列，便于后续操作。

  2. 方法一（双指针滑动窗口）

    可以将问题化简为两个「≤ 某值」的问题

    定义函数

    f(k)=#{0≤i<j<n∣nums[i]+nums[j]≤k}.f(k)=\#\{0\leq i<j<n\mid nums[i]+nums[j]\leq k\}.

    那么题目要的答案就是

    f(upper)−f(lower−1).f(upper)−f(lower−1).

    对于每个左端点 i（0 ≤ i < n-1），我们维护两个指针 l 与 r：

    • 左指针 l 从头开始（0），右指针 r 从尾开始（n−1）；

    • 如果 nums[l] + nums[r] ≤ k，那么对于固定的 l，所有 (l, l+1),…,(l, r) 都满足，因为排序保证 nums[l] + nums[j] ≤ nums[l] + nums[r]；可以一次性加上 r−l 个对，把 l 右移：l += 1。

      否则（和太大）就让 r 左移：r -= 1。

    • 直到 l >= r，整个过程需 O(n)O(n) 级的指针移动，配合排序总复杂度 O(nlog⁡n)O(n \log n)。

  3. 方法二（二分查找）
    遍历每个元素作为固定点：对于每一个元素nums[i]（其中i < j），直接对排序后的数组在区间 (i+1, n-1] 上执行两次二分查找：

    计算目标和的上下界：lower - nums[i] 和 upper - nums[i]，即要求nums[j]必须落在这个范围内。

    二分查找边界：在有序数组中利用二分查找快速定位满足条件的j的位置区间：

    枚举每个 i，目标是找满足

    lower≤nums[i]+nums[j]≤upper,j>ilower≤nums[i]+nums[j]≤upper,j>i

    等价于

    lower−nums[i]≤nums[j]≤upper−nums[i].lower−nums[i]≤nums[j]≤upper−nums[i].

    • left：在排序数组的区间 (i+1, n) 上，第一个大于等于目标下界lower - nums[i]的元素位置
      lo = lower - nums[i]，查 bisect_left(nums, lo, i+1)；
    • right：第一个大于目标上界upper - nums[i]的元素位置
      hi = upper - nums[i]，查 bisect_right(nums, hi, i+1) - 1；

    统计有效数目：计算符合条件的索引区间长度，并累加到总数中

    • 二分查找各 O(log⁡n)O(\log n)，共 O(nlog⁡n)O(n \log n)。

时间复杂度

  • 排序数组的时间为 O(nlog⁡n)O(n \log n)，其中 nn 是 nums.length
  • 双指针扫描需 O(n)O(n)
  • 遍历每个元素并进行两次二分查找的操作时间为 O(nlog⁡n)O(n \log n)
  • 两种方法总时间复杂度都为：O(nlog⁡n)O(n \log n)
  • 空间复杂度：O(n)O(n)（排序需要复制或原地排序），O(1)O(1)（忽略排序所需栈或语言内部额外空间）

代码实现

双指针法：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution:
    def countFairPairs(self, nums: list[int], lower: int, upper: int) -> int:
        # 排序
        nums.sort()
        # 结果 = ≤upper 的对数 - ≤(lower-1) 的对数
        return self._count_leq(nums, upper) - self._count_leq(nums, lower - 1)

    def _count_leq(self, nums: list[int], k: int) -> int:
        """
        返回 排序后数组中 和 <= k 的数对数量 f(k)。
        """
        l, r = 0, len(nums) - 1
        cnt = 0
        while l < r:
            if nums[l] + nums[r] <= k:
                # 对于当前 l，(l, l+1)...(l, r) 都是合法对
                cnt += (r - l)
                l += 1
            else:
                # 和太大，缩小右侧
                r -= 1
        return cnt

二分法：

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
        nums.sort()
        n = len(nums)
        count = 0
        for i in range(n - 1):
            lo = lower - nums[i]
            hi = upper - nums[i]
            left = bisect_left(nums, lo, i + 1, n)
            right = bisect_right(nums, hi, i + 1, n) - 1
            if left < n and left <= right:
                count += (right - left + 1)  # 符合条件的元素数目
        return count