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
提示:
- 按升序对数组进行排序。
- 对于数组中的每个数字,跟踪数组中可以与该数字形成公平对的最小和最大数字。
- 当您移动到更大的数字时,两个边界都会向下移动。
解决方案:
我们可以使用以下方法:
- 对数组进行排序:排序帮助我们利用双指针技术并更有效地执行二分搜索。
- 双指针技术:对于排序数组中的每个元素,我们可以计算可以与其形成公平对的元素的范围。我们使用二分搜索来找到这个范围。
- 边界二分搜索:对于每个元素 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 ?>
解释:
- 排序:我们对数组 nums 进行排序,以便更容易通过二分搜索找到有效的对。
-
二分搜索范围:
- 对于每个元素 nums[i],我们找到低值和高值,这是我们希望总和落入的范围。
- 我们使用两次二分搜索来查找索引范围 [left, right),其中 nums[i] nums[j] 落在 [lower, upper] 内。
- 计数对:我们为每个 i 添加左右之间有效索引的计数。
由于对每个元素进行排序和二分搜索,这种方法的时间复杂度为 O(n log n),这对于大型输入来说足够高效。
联系链接
如果您发现本系列有帮助,请考虑在 GitHub 上给 存储库 一个星号或在您最喜欢的社交网络上分享该帖子?。您的支持对我来说意义重大!
如果您想要更多类似的有用内容,请随时关注我:
- 领英
- GitHub
以上是计算公平对的数量的详细内容。更多信息请关注PHP中文网其他相关文章!

PHP在现代编程中仍然是一个强大且广泛使用的工具,尤其在web开发领域。1)PHP易用且与数据库集成无缝,是许多开发者的首选。2)它支持动态内容生成和面向对象编程,适合快速创建和维护网站。3)PHP的性能可以通过缓存和优化数据库查询来提升,其广泛的社区和丰富生态系统使其在当今技术栈中仍具重要地位。

在PHP中,弱引用是通过WeakReference类实现的,不会阻止垃圾回收器回收对象。弱引用适用于缓存系统和事件监听器等场景,需注意其不能保证对象存活,且垃圾回收可能延迟。

\_\_invoke方法允许对象像函数一样被调用。1.定义\_\_invoke方法使对象可被调用。2.使用$obj(...)语法时,PHP会执行\_\_invoke方法。3.适用于日志记录和计算器等场景,提高代码灵活性和可读性。

Fibers在PHP8.1中引入,提升了并发处理能力。1)Fibers是一种轻量级的并发模型,类似于协程。2)它们允许开发者手动控制任务的执行流,适合处理I/O密集型任务。3)使用Fibers可以编写更高效、响应性更强的代码。

PHP社区提供了丰富的资源和支持,帮助开发者成长。1)资源包括官方文档、教程、博客和开源项目如Laravel和Symfony。2)支持可以通过StackOverflow、Reddit和Slack频道获得。3)开发动态可以通过关注RFC了解。4)融入社区可以通过积极参与、贡献代码和学习分享来实现。

PHP和Python各有优势,选择应基于项目需求。1.PHP适合web开发,语法简单,执行效率高。2.Python适用于数据科学和机器学习,语法简洁,库丰富。

PHP不是在消亡,而是在不断适应和进化。1)PHP从1994年起经历多次版本迭代,适应新技术趋势。2)目前广泛应用于电子商务、内容管理系统等领域。3)PHP8引入JIT编译器等功能,提升性能和现代化。4)使用OPcache和遵循PSR-12标准可优化性能和代码质量。

PHP的未来将通过适应新技术趋势和引入创新特性来实现:1)适应云计算、容器化和微服务架构,支持Docker和Kubernetes;2)引入JIT编译器和枚举类型,提升性能和数据处理效率;3)持续优化性能和推广最佳实践。


热AI工具

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

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

Undress AI Tool
免费脱衣服图片

Clothoff.io
AI脱衣机

AI Hentai Generator
免费生成ai无尽的。

热门文章

热工具

SublimeText3 Linux新版
SublimeText3 Linux最新版

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

ZendStudio 13.5.1 Mac
功能强大的PHP集成开发环境

SecLists
SecLists是最终安全测试人员的伙伴。它是一个包含各种类型列表的集合,这些列表在安全评估过程中经常使用,都在一个地方。SecLists通过方便地提供安全测试人员可能需要的所有列表,帮助提高安全测试的效率和生产力。列表类型包括用户名、密码、URL、模糊测试有效载荷、敏感数据模式、Web shell等等。测试人员只需将此存储库拉到新的测试机上,他就可以访问到所需的每种类型的列表。

SublimeText3汉化版
中文版,非常好用