php leetcode实践【一】 两数之和

1.题目   a+b = c ,a b c的取值为正负10的9次方。数组d 拥有一万个不重复的值，a和b是d中的值，c是一个随机数，求a和b的下标。

2.解法

2.1复杂度最高 两个for循环

<?PHP


$time1 = microtime_float();
$mem1 = memory_get_usage();


$nums = [];
for ($i=0; $i < 10000; $i++) { 
	$nums[] = mt_rand(-1000000000,1000000000);
}
$target = $nums[9999] + $nums[9998];

$time2 = microtime_float();
$mem2 = memory_get_usage();

echo '生成数据用时：',($time2 - $time1)*1000,'毫秒',"\r\n";
echo '生成数据用内存：',($mem2 - $mem1)/1024,'Kb',"\r\n";

foreach ($nums as $k1 => $v1) {
	$v2 = $target - $v1;
	if($v1 == $v2){
		continue;
	}
	for ($i=0; $i < 10000; $i++) { 
		if($nums[$i] == $v2){
			echo '数值：',$v1,',',$nums[$k2],',',$target,"\r\n";
			echo '结果：',$k1,',',$i,"\r\n";
			break;
		}
	}
}

$time3 = microtime_float();
$mem3 = memory_get_usage();
echo '计算用时：',($time3 - $time2)*1000,'毫秒',"\r\n";
echo '计算用内存：',($mem3 - $mem2)/1024,'Kb',"\r\n";

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

结果

生成数据用时：8.3839893341064毫秒
生成数据用内存：388.046875Kb
数值：-535137412,,136037086
结果：9998,9999
数值：671174498,,136037086
结果：9999,9998
计算用时：17506.166934967毫秒
计算用内存：0.03125Kb

2.2稍微优化一点 第二个for的开始值

<?PHP


$time1 = microtime_float();
$mem1 = memory_get_usage();


$nums = [];
for ($i=0; $i < 10000; $i++) { 
	$nums[] = mt_rand(-1000000000,1000000000);
}
$target = $nums[9999] + $nums[9998];

$time2 = microtime_float();
$mem2 = memory_get_usage();

echo '生成数据用时：',($time2 - $time1)*1000,'毫秒',"\r\n";
echo '生成数据用内存：',($mem2 - $mem1)/1024,'Kb',"\r\n";

foreach ($nums as $k1 => $v1) {
	$v2 = $target - $v1;
	if($v1 == $v2){
		continue;
	}
	for ($i=$k1+1; $i < 10000; $i++) { 
		if($nums[$i] == $v2){
			echo '数值：',$v1,',',$nums[$k2],',',$target,"\r\n";
			echo '结果：',$k1,',',$i,"\r\n";
			break;
		}
	}
}

$time3 = microtime_float();
$mem3 = memory_get_usage();
echo '计算用时：',($time3 - $time2)*1000,'毫秒',"\r\n";
echo '计算用内存：',($mem3 - $mem2)/1024,'Kb',"\r\n";

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

结果

生成数据用时：8.9809894561768毫秒
生成数据用内存：388.046875Kb
数值：-433743277,,-1261371475
结果：9998,9999
计算用时：8538.6850833893毫秒
计算用内存：0.03125Kb

2.3 使用php自带函数 in_array

<?PHP


$time1 = microtime_float();
$mem1 = memory_get_usage();


$nums = [];
for ($i=0; $i < 10000; $i++) { 
	$nums[] = mt_rand(-1000000000,1000000000);
}
$target = $nums[9999] + $nums[9998];

$time2 = microtime_float();
$mem2 = memory_get_usage();

echo '生成数据用时：',($time2 - $time1)*1000,'毫秒',"\r\n";
echo '生成数据用内存：',($mem2 - $mem1)/1024,'Kb',"\r\n";

foreach ($nums as $k1 => $v1) {
	$v2 = $target - $v1;
	if($v1 == $v2){
		continue;
	}
	if(in_array($v2, $nums)){
		echo '数值：',$v1,',',$v2,',',$target,"\r\n";
		echo '结果：',$k1,',',array_keys($nums,$v2)[0],"\r\n";
		break;
	}
}

$time3 = microtime_float();
$mem3 = memory_get_usage();
echo '计算用时：',($time3 - $time2)*1000,'毫秒',"\r\n";
echo '计算用内存：',($mem3 - $mem2)/1024,'Kb',"\r\n";

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

结果

生成数据用时：8.3198547363281毫秒
生成数据用内存：388.046875Kb
数值：768523606,-437991916,330531690
结果：9998,9999
计算用时：128.56221199036毫秒
计算用内存：0.03125Kb

2.4 使用类似hash的方式 目前最快的，但是占用内存大

<?PHP


$time1 = microtime_float();
$mem1 = memory_get_usage();


$nums = [];
for ($i=0; $i < 10000; $i++) { 
	$nums[] = mt_rand(-1000000000,1000000000);
}
$target = $nums[9999] + $nums[9998];

$time2 = microtime_float();
$mem2 = memory_get_usage();

echo '生成数据用时：',($time2 - $time1)*1000,'毫秒',"\r\n";
echo '生成数据用内存：',($mem2 - $mem1)/1024,'Kb',"\r\n";


$map = [];
foreach ($nums as $k => $v) {
	$map[$v] = $k;
}
foreach ($nums as $k1 => $v1) {
	$k2 = $map[$target - $v1];
	if($k2 && $v1*2 != $target){
		echo '数值：',$v1,',',$nums[$k2],',',$target,"\r\n";
		echo '结果：',$k1,',',$k2,"\r\n";
		break;
	}
}

$time3 = microtime_float();
$mem3 = memory_get_usage();
echo '计算用时：',($time3 - $time2)*1000,'毫秒',"\r\n";
echo '计算用内存：',($mem3 - $mem2)/1024,'Kb',"\r\n";

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

结果

生成数据用时：8.4319114685059毫秒
生成数据用内存：388.046875Kb
数值：-170856604,768988391,598131787
结果：9998,9999
计算用时：12.870073318481毫秒
计算用内存：512.078125Kb

2.5 优化一下内存的占用问题

<?PHP


$time1 = microtime_float();
$mem1 = memory_get_usage();


$nums = [];
for ($i=0; $i < 10000; $i++) { 
	$nums[] = mt_rand(-1000000000,1000000000);
}
$target = $nums[9999] + $nums[9998];

$time2 = microtime_float();
$mem2 = memory_get_usage();

echo '生成数据用时：',($time2 - $time1)*1000,'毫秒',"\r\n";
echo '生成数据用内存：',($mem2 - $mem1)/1024,'Kb',"\r\n";


$map = [];
foreach ($nums as $k => $v) {
	$v2 = $target - $v;
	if($v2 == $v){
		continue;
	}
	$k2 = $map[$v2];
	if($k2){
		echo '数值：',$v,',',$v2,',',$target,"\r\n";
		echo '结果：',$k,',',$k2,"\r\n";
		break;
	}
	$map[$v] = $k;
}

$time3 = microtime_float();
$mem3 = memory_get_usage();
echo '计算用时：',($time3 - $time2)*1000,'毫秒',"\r\n";
echo '计算用内存：',($mem3 - $mem2)/1024,'Kb',"\r\n";

function microtime_float()
{
    list($usec, $sec) = explode(" ", microtime());
    return ((float)$usec + (float)$sec);
}

结果，和2.4差不多。如果a和b不是取下标 9998和9999的话，能明显看出区别

生成数据用时：7.8308582305908毫秒
生成数据用内存：388.046875Kb
数值：-974116326,269553254,-704563072
结果：9999,9998
计算用时：12.427091598511毫秒
计算用内存：512.078125Kb

下面是 下标为10和20的结果，内存占用区别很明显

$target = $nums[10] + $nums[20];

本文为看恩吧原创文章,转载无需和我联系,但请注明来自knsay.com

打赏

• 上一篇： 【五】从零搭建react-新 增加富文本组件
• 下一篇： 【六】从零搭建react-新 实现菜单和路由统一管理