内容简介: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
以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持 码农网
猜你喜欢:- LeetCode算法系列_0891_子序列宽度之和
- Go语言性能优化-两数之和算法性能研究
- LeetCode-1-两数之和
- Leetcode 1:两数之和
- LeetCode题解 - 1. 两数之和
- LeetCode 第 1 号问题:两数之和
本站部分资源来源于网络,本站转载出于传递更多信息之目的,版权归原作者或者来源机构所有,如转载稿涉及版权问题,请联系我们。