2563. 统计公平数对的数目

🟠   🔖  数组 双指针 二分查找 排序  🔗 力扣 LeetCode

题目

Given a 0-indexed integer array nums of size n and two integers lower and upper, return the number of fair pairs.

A pair (i, j) is fair if:

• 0 <= i < j < n, and
• lower <= nums[i] + nums[j] <= upper

Example 1:

Input: nums = [0,1,7,4,4,5], lower = 3, upper = 6

Output: 6

Explanation: There are 6 fair pairs: (0,3), (0,4), (0,5), (1,3), (1,4), and (1,5).

Example 2:

Input: nums = [1,7,9,2,5], lower = 11, upper = 11

Output: 1

Explanation: There is a single fair pair: (2,3).

Constraints:

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

题目大意

给你一个下标从 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

解题思路

1. 排序数组: 首先对数组 nums 进行排序，排序后的数组可以帮助我们在一段连续区域内利用二分查找快速找到满足特定和的数对。

2. 双指针遍历数组: 遍历排序后的数组，对每个 nums[i]，希望找到 nums[j]，满足 lower - nums[i] <= nums[j] <= upper - nums[i]。

3. 使用二分查找定位范围:

   • 对于每个 i：
     • 使用 lowerBound 函数在 i+1 到末尾的范围内找到第一个满足 nums[j] >= lower - nums[i] 的位置。
     • 使用 upperBound 函数在 i+1 到末尾的范围内找到第一个不满足 nums[j] <= upper - nums[i] 的位置。
   • lowerBound 返回的索引为符合条件的 j 值的起始位置，而 upperBound 返回的是结束位置（不包含在范围内）。
   • 两个索引的差值 up - low 即为当前 i 下满足条件的 j 数量。

4. 结果累加: 对于每个 i，累加 up - low 到结果 res 中。

复杂度分析

• 时间复杂度：O(n log n)。
  • 排序的时间复杂度是 O(n log n)。
  • 外层循环遍历 nums 需要 O(n) 次，每次调用 lowerBound 和 upperBound 都是 O(log n) 的时间复杂度，因此双指针的复杂度是 O(n log n)。
  • 总体时间复杂度为 O(n log n)。
• 空间复杂度：O(1)，只用了常数级额外空间（不考虑排序空间开销）。

代码

/**
 * @param {number[]} nums
 * @param {number} lower
 * @param {number} upper
 * @return {number}
 */
var countFairPairs = function (nums, lower, upper) {
	// 1. 对 nums 进行排序
	nums.sort((a, b) => a - b);

	let res = 0;
	// 2. 遍历 nums，将 nums 中的每个元素作为起始点
	for (let i = 0; i < nums.length - 1; i++) {
		// 3. 使用二分查找满足条件的起始位置和结束位置（不包含在范围内）
		const low = lowerBound(nums, lower - nums[i], i + 1);
		const up = upperBound(nums, upper - nums[i], i + 1);

		// 4. 将满足条件的公平数对数量加入 res 中
		res += up - low;
	}
	return res;
};

// 辅助函数，找到第一个使得 nums[index] >= target 的 index
var lowerBound = function (nums, target, start) {
	let end = nums.length;
	while (start < end) {
		let mid = ((start + end) / 2) | 0;
		if (nums[mid] >= target) {
			end = mid;
		} else {
			start = mid + 1;
		}
	}
	return start;
};

// 辅助函数，找到第一个使得 nums[index] > target 的 index
var upperBound = function (nums, target, start) {
	let end = nums.length;
	while (start < end) {
		let mid = ((start + end) / 2) | 0;
		if (nums[mid] > target) {
			end = mid;
		} else {
			start = mid + 1;
		}
	}
	return start;
};

相关题目

题号	标题	题解	标签	难度	力扣
327	区间和的个数		树状数组 线段树 数组 4+	🔴	🀄️ 🔗
1865	找出和为指定值的下标对		设计 数组 哈希表	🟠	🀄️ 🔗
2006	差的绝对值为 K 的数对数目		数组 哈希表 计数	🟢	🀄️ 🔗
2824	统计和小于目标的下标对数目		数组 双指针 二分查找 1+	🟢	🀄️ 🔗