搜索
首页后端开发php教程计算公平对的数量

Count the Number of Fair Pairs

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
  • -109 9
  • -109 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中文网其他相关文章!

声明
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系admin@php.cn
简单地说明PHP会话的概念。简单地说明PHP会话的概念。Apr 26, 2025 am 12:09 AM

phpsessionstrackuserdataacrossmultiplepagerequestsusingauniqueIdStoredInacookie.here'showtomanageThemeffectionaly:1)startAsessionWithSessionwwithSession_start()和stordoredAtain $ _session.2)

您如何循环中存储在PHP会话中的所有值?您如何循环中存储在PHP会话中的所有值?Apr 26, 2025 am 12:06 AM

在PHP中,遍历会话数据可以通过以下步骤实现:1.使用session_start()启动会话。2.通过foreach循环遍历$_SESSION数组中的所有键值对。3.处理复杂数据结构时,使用is_array()或is_object()函数,并用print_r()输出详细信息。4.优化遍历时,可采用分页处理,避免一次性处理大量数据。这将帮助你在实际项目中更有效地管理和使用PHP会话数据。

说明如何使用会话进行用户身份验证。说明如何使用会话进行用户身份验证。Apr 26, 2025 am 12:04 AM

会话通过服务器端的状态管理机制实现用户认证。1)会话创建并生成唯一ID,2)ID通过cookies传递,3)服务器存储并通过ID访问会话数据,4)实现用户认证和状态管理,提升应用安全性和用户体验。

举一个如何在PHP会话中存储用户名的示例。举一个如何在PHP会话中存储用户名的示例。Apr 26, 2025 am 12:03 AM

Tostoreauser'snameinaPHPsession,startthesessionwithsession_start(),thenassignthenameto$_SESSION['username'].1)Usesession_start()toinitializethesession.2)Assigntheuser'snameto$_SESSION['username'].Thisallowsyoutoaccessthenameacrossmultiplepages,enhanc

哪些常见问题会导致PHP会话失败?哪些常见问题会导致PHP会话失败?Apr 25, 2025 am 12:16 AM

PHPSession失效的原因包括配置错误、Cookie问题和Session过期。1.配置错误:检查并设置正确的session.save_path。2.Cookie问题:确保Cookie设置正确。3.Session过期:调整session.gc_maxlifetime值以延长会话时间。

您如何在PHP中调试与会话相关的问题?您如何在PHP中调试与会话相关的问题?Apr 25, 2025 am 12:12 AM

在PHP中调试会话问题的方法包括:1.检查会话是否正确启动;2.验证会话ID的传递;3.检查会话数据的存储和读取;4.查看服务器配置。通过输出会话ID和数据、查看会话文件内容等方法,可以有效诊断和解决会话相关的问题。

如果session_start()被多次调用会发生什么?如果session_start()被多次调用会发生什么?Apr 25, 2025 am 12:06 AM

多次调用session_start()会导致警告信息和可能的数据覆盖。1)PHP会发出警告,提示session已启动。2)可能导致session数据意外覆盖。3)使用session_status()检查session状态,避免重复调用。

您如何在PHP中配置会话寿命?您如何在PHP中配置会话寿命?Apr 25, 2025 am 12:05 AM

在PHP中配置会话生命周期可以通过设置session.gc_maxlifetime和session.cookie_lifetime来实现。1)session.gc_maxlifetime控制服务器端会话数据的存活时间,2)session.cookie_lifetime控制客户端cookie的生命周期,设置为0时cookie在浏览器关闭时过期。

See all articles

热AI工具

Undresser.AI Undress

Undresser.AI Undress

人工智能驱动的应用程序,用于创建逼真的裸体照片

AI Clothes Remover

AI Clothes Remover

用于从照片中去除衣服的在线人工智能工具。

Undress AI Tool

Undress AI Tool

免费脱衣服图片

Clothoff.io

Clothoff.io

AI脱衣机

Video Face Swap

Video Face Swap

使用我们完全免费的人工智能换脸工具轻松在任何视频中换脸!

热工具

安全考试浏览器

安全考试浏览器

Safe Exam Browser是一个安全的浏览器环境,用于安全地进行在线考试。该软件将任何计算机变成一个安全的工作站。它控制对任何实用工具的访问,并防止学生使用未经授权的资源。

SublimeText3 Mac版

SublimeText3 Mac版

神级代码编辑软件(SublimeText3)

DVWA

DVWA

Damn Vulnerable Web App (DVWA) 是一个PHP/MySQL的Web应用程序,非常容易受到攻击。它的主要目标是成为安全专业人员在合法环境中测试自己的技能和工具的辅助工具,帮助Web开发人员更好地理解保护Web应用程序的过程,并帮助教师/学生在课堂环境中教授/学习Web应用程序安全。DVWA的目标是通过简单直接的界面练习一些最常见的Web漏洞,难度各不相同。请注意,该软件中

EditPlus 中文破解版

EditPlus 中文破解版

体积小,语法高亮,不支持代码提示功能

VSCode Windows 64位 下载

VSCode Windows 64位 下载

微软推出的免费、功能强大的一款IDE编辑器