php算法题：两数之和

Ververica 发布于2019-07-01 12:43 / 3376人阅读

摘要：一两遍循环，暴力破解代码如下时间复杂度提交，结果执行时间。。。。。可以说龟速了二两遍这个方法是看了的解决方案，但它是代码，开始不知道，其实的数组就是实现的，后面看了下面两片文章的介绍，才理解，解决的。

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
时间复杂度 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

混合云 idc机房托管回文数之和 php javascript算法题字符串算法题最难的算法题

文章版权归作者所有，未经允许请勿转载,若此文章存在违规行为，您可以联系管理员删除。

转载请注明本文地址：https://www.ucloud.cn/yun/31350.html

算法题-两数之和

摘要：题目描述给出两个非空的链表用来表示两个非负的整数。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字之外，这两个数都不会以开头。题目描述：给出两个非空的链表用来表示两个非负的整数。其中，它们各自的位数是按照逆序的方式存储的，并且它们的每个节点只能存储一位数字。如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除...

Vicky 2019-08-26 10:29 评论0 收藏0
【前端来刷LeetCode】两数之和与两数相加

摘要：给定表，存在函数，对任意给定的关键字值，代入函数后若能得到包含该关键字的记录在表中的地址，则称表为哈希表，函数为哈希函数。而中的对象就是基于哈希表结构，所以我们构造一个对象即可，是当前遍历到的值，是其与目标值的差。大部分玩前端的小伙伴，在算法上都相对要薄弱些，毕竟调样式、调兼容就够掉头发的了，哪还有多余的头发再去折腾。确实在前端中需要使用到算法的地方是比较少，但若要往高级方向发展，...

BLUE 2019-08-26 13:53 评论0 收藏0
【刷算法】LeetCode- 两数之和

摘要：题目描述给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。题目描述给定一个整数数组和一个目标值，找出数组中和为目标值的两个数。你可以假设每个输入只对应一种答案，且同样的元素不能被重复利用。示例: 给定 nums = [2, 7, 11, 15], target = 9 因为 nums[0] + nums[...

superw 2019-08-23 10:27 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

张春雷 2019-08-16 18:29 评论0 收藏0
LeetCode 167：两数之和 II - 输入有序数组 Two Sum II - Input a

摘要：公众号爱写给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值和，其中必须小于。示例输入输出解释与之和等于目标数。公众号：爱写bug（ID：icodebugs）给定一个已按照升序排列的有序数组，找到两个数使得它们相加之和等于目标数。函数应该返回这两个下标值 index1 和 index2，其中 index1 必须小于 index2。...

Me_Kun 2019-07-31 11:26 评论0 收藏0