php如何求三个数之和?三数之和问题详解
Admin 2021-04-28 群英技术资讯 2174 次浏览
php如何求三个数之和?这篇文章主要给大家分享一个PHP求三数之和问题的实例,以下是问题描述,正在学习PHP的朋友,可以尝试实现一下,本文有现实思路及代码可参考。
三数之和
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有满足条件且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例:
给定数组 nums = [-1, 0, 1, 2, -1, -4], 满足要求的三元组集合为: [ [-1, 0, 1], [-1, -1, 2] ]
解题思路 1
暴力枚举法,三层 for + if 判断就可以了,这样作面试中 offer 会成为别人的。 不写代码了,数据量大了也容易超时。
解题思路 2
可以先固定一个值,然后寻找后两个值时可采取双指针的方法,将总的时间复杂度优化到 O(n^2)。实现的过程中,要注意优化以及去重。
首先我们先对原数组进行排序,这样可以把重复的值集中到一起,便于去重。
确定第一个元素时,如果它已经比 0 大了,那么可以直接跳出循环,因为后面的数字都比它大。如 [1, 2, 3, 4], i = 0, nums[i] > 0, 这样是不可能产生合法的情况的,直接 break。
确定第一个元素时,如果发现它与它前面的值一样,那么跳过本轮。如 [-1, -1, 0, 1], 在第一轮后,已经选出了 {-1, 0, 1}, 现在 i = 1,nums[i] == nums[i - 1], 为了避免重复,直接 continue。
接下来利用双指针,left 指向 i + 1, right 指向 count($nums) - 1。逐个进行判断,并注意去重。有点类似于固定在一个值,然后剩下的用双指针求两数之和。
class Solution {
/** * @param Integer[] $nums * @return Integer[][] */
function threeSum($nums) {
$result = [];
$count = count($nums);
if ($nums === null || count($nums) <= 2) return $result;
sort($nums); // O(nlogn)
for ($i = 0; $i < $count - 2; $i++) { // O(n^2)
if ($nums[$i] > 0) break; // 第一个数大于 0,后面的数都比它大,肯定不成立了
if ($i > 0 && $nums[$i] === $nums[$i - 1]) continue; // 去掉重复情况
$target = -$nums[$i];
$left = $i + 1;
$right = $count - 1;
while ($left < $right) {
if ($nums[$left] + $nums[$right] === $target) {
$result[] = [$nums[$i], $nums[$left], $nums[$right]];
// 现在要增加 left,减小 right,但是不能重复,比如: [-2, -1, -1, -1, 3, 3, 3], i = 0, left = 1, right = 6, [-2, -1, 3] 的答案加入后,需要排除重复的 -1 和 3
$left++;
$right--; // 首先无论如何先要进行加减操作
while ($left < $right && $nums[$left] === $nums[$left - 1]) $left++;
while ($left < $right && $nums[$right] === $nums[$right + 1]) $right--;
} else if ($nums[$left] + $nums[$right] < $target) {
$left++;
} else { // $nums[$left] + $nums[$right] > $target
$right--;
}
}
}
return $result;
}
}
以上就是关于php求三个数之和问题的介绍,上述代码仅供参考,希望对大家学习有帮助,更多PHP内容大家可以关注其他文章。
免责声明:本站发布的内容(图片、视频和文字)以原创、转载和分享为主,文章观点不代表本网站立场,如果涉及侵权请联系站长邮箱:mmqy2019@163.com进行举报,并提供相关证据,查实之后,将立刻删除涉嫌侵权内容。
猜你喜欢
查看php-fpm占用内存怎样做,用什么方法?一些朋友可能会遇到这方面的问题,对此在下文小编向大家来讲解一下,内容详细,易于理解,希望大家阅读完这篇能有收获哦,有需要的朋友就往下看吧!
PHP 是解释型语言,其执行过程需先编译成中间代码,再经由特定的虚拟机,翻译成特定的指令被执行。其执行过程如下:PHP 代码 => Token => 抽象语法树 => Opcodes => 执行。
php伪静态是什么?可能很多朋友听过动态,静态和伪静态这些词,但是对于伪静态究竟是什么并不清楚,因此这篇文章就给大家介绍一下什么是PHP伪静态。
PHP-验证名称以下代码将通过简单的方式来检测name字段是否包含字母和空格,如果name字段值不合法,将输出错误信息:$name=test_input($_POST[
所谓的代码分离其实只是一种思路,既然是一种思路那就意味着他是有需求的没有需求就没有解决方案没有方案就不存在思路。在这之前,我们制作PHP程序页面的时候。都是HTML和PHP混合写在一起的。这产生了什么样的问题,主要有两个:1、代码太长不便阅读,一个流程往往跨了N行代码,可能之后还需要几个括号结束都不记得了。。2、不便于编辑网页,我们制作网页的时候。往往是先用DW等工
成为群英会员,开启智能安全云计算之旅
立即注册关注或联系群英网络
7x24小时售前:400-678-4567
7x24小时售后:0668-2555666
24小时QQ客服
群英微信公众号
CNNIC域名投诉举报处理平台
服务电话:010-58813000
服务邮箱:service@cnnic.cn
投诉与建议:0668-2555555
Copyright © QY Network Company Ltd. All Rights Reserved. 2003-2020 群英 版权所有
增值电信经营许可证 : B1.B2-20140078 ICP核准(ICP备案)粤ICP备09006778号 域名注册商资质 粤 D3.1-20240008