计算公平对的数量

2563。计算公平对的数量

难度：中等

主题：数组、两个指针、二分查找、排序

给定一个 0 索引的 大小为 n 的整数数组 nums 和两个上下整数，返回 公平对的数量 .

一对 (i, j) 是 公平如果：

• 0
• 下

示例1：

• 输入： nums = [0,1,7,4,4,5]，下= 3，上= 6
• 输出： 6
• 解释： 有 6 个公平对：(0,3)、(0,4)、(0,5)、(1,3)、(1,4) 和 (1,5) .

示例2：

• 输入： nums = [1,7,9,2,5]，下= 11，上= 11
• 输出： 1
• 解释： 有一个公平对：(2,3)。

约束：

• 1 5
• nums.length == n
• -10⁹ 9
• -10⁹ 9

提示：

1. 按升序对数组进行排序。
2. 对于数组中的每个数字，跟踪数组中可以与该数字形成公平对的最小和最大数字。
3. 当您移动到更大的数字时，两个边界都会向下移动。

解决方案：

我们可以使用以下方法：

1. 对数组进行排序：排序帮助我们利用双指针技术并更有效地执行二分搜索。
2. 双指针技术：对于排序数组中的每个元素，我们可以计算可以与其形成公平对的元素的范围。我们使用二分搜索来找到这个范围。
3. 边界二分搜索：对于每个元素 nums[i]，查找范围 [lower, upper] - nums[i]，其中 j > ；我。我们使用二分搜索来查找满足此范围的最小和最大索引。

让我们用 PHP 实现这个解决方案：2563。计算公平对的数量

<?php
/**
* @param Integer[] $nums
* @param Integer $lower
* @param Integer $upper
* @return Integer
*/
function countFairPairs($nums, $lower, $upper) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
* Helper function for binary search to find left boundary
*
* @param $arr
* @param $target
* @param $start
* @return int|mixed
*/
function lowerBound($arr, $target, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

/**
* Helper function for binary search to find right boundary
*
* @param $arr
* @param $target
* @param $start
* @return int|mixed
*/
function upperBound($arr, $target, $start) {
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Example usage:
$nums = [0, 1, 7, 4, 4, 5];
$lower = 3;
$upper = 6;
echo countFairPairs($nums, $lower, $upper);  // Output: 6
?>

解释：

1. 排序：我们对数组 nums 进行排序，以便更容易通过二分搜索找到有效的对。
2. 二分搜索范围：
   • 对于每个元素 nums[i]，我们找到低值和高值，这是我们希望总和落入的范围。
   • 我们使用两次二分搜索来查找索引范围 [left, right)，其中 nums[i] nums[j] 落在 [lower, upper] 内。
3. 计数对：我们为每个 i 添加左右之间有效索引的计数。

由于对每个元素进行排序和二分搜索，这种方法的时间复杂度为 O(n log n)，这对于大型输入来说足够高效。

联系链接

如果您发现本系列有帮助，请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子？。您的支持对我来说意义重大！

如果您想要更多类似的有用内容，请随时关注我：

• 领英
• GitHub

以上是计算公平对的数量的详细内容。更多信息请关注PHP中文网其他相关文章！