算法题:两数之和

栏目: 编程工具 · 发布时间: 5年前

内容简介:Given an array of integers, return indices of the two numbers such that they add up to a specific target.You may assume that each input would have exactly one solution, and you may not use the same element twice.Example:

1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example:

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].

一、两遍循环,暴力破解

代码如下

function twoSum($nums, $target) {
        for($i=0;$i<count($nums); $i++){
            for($j=$i+1; $j<count($nums); $j++){
                $sum = $nums[$i]+$nums[$j];
                if($target == $sum){
                    return array($i,$j);
                }
            }
        }
    }

时间复杂度 O(n^2 )

提交,结果执行时间1968 ms。。。。。

可以说龟速了

二、两遍hash

这个方法是看了leetcode的解决方案,但它是 java 代码,开始不知道,其实 php 的数组就是hash实现的,后面看了下面两片文章的介绍,才理解,解决的。

https://www.cnblogs.com/s-b-b...

https://www.cnblogs.com/shang...

代码如下

function twoSum2(array $nums , $target)
{
    $res = [];
    $nums_match = [];
    foreach ($nums as $nums_k => $nums_v){
        if(!isset($nums_match[$target-$nums_v])){
            $nums_match[$target-$nums_v] = $nums_k;
        }
    }
    
    foreach ($nums as $nums_k => $nums_v){
        if (isset($nums_match[$nums_v]) && $nums_match[$nums_v] != $nums_k) {
            $res[] = $nums_k;
            $res[] = $nums_match[$nums_v];
            return $res;
        }
    }
}

时间复杂度O(n)

执行时间24 ms ,提升很大

三、一遍hash

这是在两边hash的基础上进行的优化

代码如下

function twoSum($nums, $target) {
        $nums_match = [];
        foreach ($nums as $nums_k => $nums_v){
            if((isset($nums_match[$target-$nums_v]))){
                return array($nums_match[$target-$nums_v],$nums_k);
            }
            $nums_match[$nums_v] = $nums_k;
        }

    }

时间复杂度O(n)

执行时间16 ms


以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网

查看所有标签

猜你喜欢:

本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们

自制搜索引擎

自制搜索引擎

[日]山田浩之、[日]末永匡 / 胡屹 / 人民邮电出版社 / 2016-1 / 39.00元

《自制搜索引擎》聚焦于Google和Yahoo!等Web搜索服务幕后的搜索引擎系统,首先讲解了搜索引擎的基础知识和原理,接着以现实中的开源搜索引擎Senna/Groonga为示例,使用该引擎的源代码引导读者亲自体验搜索引擎的开发过程。这部分讲解涉及了倒排索引的制作和压缩、检索的处理流程以及搜索引擎的优化等内容。又简单介绍了一些更加专业的搜索引擎的知识和要点,为读者今后进一步学习打下了基础。本书适合......一起来看看 《自制搜索引擎》 这本书的介绍吧!

HTML 压缩/解压工具
HTML 压缩/解压工具

在线压缩/解压 HTML 代码

XML、JSON 在线转换
XML、JSON 在线转换

在线XML、JSON转换工具

HEX CMYK 转换工具
HEX CMYK 转换工具

HEX CMYK 互转工具