Question

2563. 统计公平数对的数目

English Version

题目描述

给你一个下标从 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 <= 105
• nums.length == n
• -109 <= nums[i] <= 109
• -109 <= lower <= upper <= 109

解法

方法一：排序 + 二分查找

我们先对数组 nums 按照升序排序，然后枚举 nums[i]，对于每个 nums[i]，我们通过二分查找找到 nums[j] 的下界 j，即第一个满足 nums[j] >= lower - nums[i] 的下标，然后再通过二分查找找到 nums[k] 的下界 k，即第一个满足 nums[k] >= upper - nums[i] + 1 的下标，那么 [j, k) 即为 nums[j] 满足 lower <= nums[i] + nums[j] <= upper 的下标范围，这些下标对应的 nums[j] 的个数即为 k - j，将其累加到答案中即可。注意 $j \gt i$。

时间复杂度 $O(n \times \log n)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组 nums 的长度。

class Solution:
  def countFairPairs(self, nums: List[int], lower: int, upper: int) -> int:
    nums.sort()
    ans = 0
    for i, x in enumerate(nums):
      j = bisect_left(nums, lower - x, lo=i + 1)
      k = bisect_left(nums, upper - x + 1, lo=i + 1)
      ans += k - j
    return ans

class Solution {
  public long countFairPairs(int[] nums, int lower, int upper) {
    Arrays.sort(nums);
    long ans = 0;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      int j = search(nums, lower - nums[i], i + 1);
      int k = search(nums, upper - nums[i] + 1, i + 1);
      ans += k - j;
    }
    return ans;
  }

  private int search(int[] nums, int x, int left) {
    int right = nums.length;
    while (left < right) {
      int mid = (left + right) >> 1;
      if (nums[mid] >= x) {
        right = mid;
      } else {
        left = mid + 1;
      }
    }
    return left;
  }
}

class Solution {
public:
  long long countFairPairs(vector<int>& nums, int lower, int upper) {
    long long ans = 0;
    sort(nums.begin(), nums.end());
    for (int i = 0; i < nums.size(); ++i) {
      auto j = lower_bound(nums.begin() + i + 1, nums.end(), lower - nums[i]);
      auto k = lower_bound(nums.begin() + i + 1, nums.end(), upper - nums[i] + 1);
      ans += k - j;
    }
    return ans;
  }
};

func countFairPairs(nums []int, lower int, upper int) (ans int64) {
  sort.Ints(nums)
  for i, x := range nums {
    j := sort.Search(len(nums), func(h int) bool { return h > i && nums[h] >= lower-x })
    k := sort.Search(len(nums), func(h int) bool { return h > i && nums[h] >= upper-x+1 })
    ans += int64(k - j)
  }
  return
}

function countFairPairs(nums: number[], lower: number, upper: number): number {
  const search = (x: number, l: number): number => {
    let r = nums.length;
    while (l < r) {
      const mid = (l + r) >> 1;
      if (nums[mid] >= x) {
        r = mid;
      } else {
        l = mid + 1;
      }
    }
    return l;
  };

  nums.sort((a, b) => a - b);
  let ans = 0;
  for (let i = 0; i < nums.length; ++i) {
    const j = search(lower - nums[i], i + 1);
    const k = search(upper - nums[i] + 1, i + 1);
    ans += k - j;
  }
  return ans;
}