两数之和解题笔记

每日一刷,用PHP和GO分别实现了2种我能想到的和官方给出的最优解。

题目

给定一个整数数组 nums 和一个目标值 target,请你在该数组中找出和为目标值的那 两个 整数,并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]

解题

PHP

穷举

思路 : 2个循环遍历一一对应,简单暴力

1
2
3
4
5
6
7
8
9
10
11
12
function twoSum($nums, $target) {
foreach ($nums as $k => $v) {
foreach ($nums as $kk => $vv) {
if ($v + $vv == $target) {
if ($k != $kk) {
return [$k,$kk];
}
}
}
}
return false;
}

时间复杂度 o(n^2),平均执行时间 1533.6ms 平均内存消耗15.96MB

使用array_search查找

思路:PHP提供了超多的数组函数,比其他语言方便了很多。

  1. 循环取数
  2. 求差
  3. array_search查找是否存在
1
2
3
4
5
6
7
8
9
10
11
12
function twoSum ($nums, $target) {
foreach ($nums as $k => $v) {
$temp = $target - $v;
unset($nums[$k]);
$kk = array_search($temp, $nums);
if ($kk != false) {
return [$k,$kk];
}

}
return false;
}

时间复杂度 o(n),平均执行时间 116ms 平均内存消耗15.94MB

Hashmap

hash表其实就是键值对的形式,在php中可以用数组来实现

  1. 循环等量的 内容长度
  2. 生成一个 数值为键,下标为值的hashmap
  3. 在循环中查找hashmap是否有差值对应
  4. 有就返回,没有把当前值写入hashmap的key下标写入value

这样做虽然时间复杂度也是o(n),但是节省了array_search的函数开销,hashmap中查找的时间复杂度是o(1)

1
2
3
4
5
6
7
8
9
10
11
12
function twoSum ($nums, $target) {

$diff = array();
for ($i = 0; $i < count($nums); $i++) {
$key = $diff[$target - $nums[$i]];
if (!isset($key)) {
$diff[$nums[$i]] = $i;
} else {
return [$key,$i];
}
}
}

时间复杂度 o(n),平均执行时间 18.4ms 平均内存消耗16.06MB

go

go 没有原生函数支持是否存在切片或者数组中,所以这边只试了2种解法

穷举

1
2
3
4
5
6
7
8
9
10
11
12
13
func twoSum(nums []int, target int) []int {
for k,v := range nums{
temp := target - v
for kk,vv := range nums{
if temp == vv {
if (k != kk){
return []int{k,kk}
}
}
}
}
return []int{}
}

时间复杂度 o(n^2),平均执行时间 36ms 平均内存消耗2.9MB

Hashmap

1
2
3
4
5
6
7
8
9
10
11
12
function twoSum ($nums, $target) {
$diff = array();
for ($i = 0; $i < count($nums); $i++) {
$key = $diff[$target - $nums[$i]];
if (!isset($key)) {
$diff[$nums[$i]] = $i;
} else {
return [$key,$i];
}
}
}

时间复杂度 o(n),平均执行时间 4ms 平均内存消耗3.8MB

ps: 那个0ms应该是抽了就不算进去了

性能对比

算法 语言 平均执行时间 平均内存
穷举 PHP 1533.6ms 15.96MB
穷举 GO 36ms 2.9MB
Hashmap PHP 18.4ms 16.06MB
Hashmap GO 4ms 3.8MB
array_search PHP 116ms 15.94MB
  • 版权声明: 本博客所有文章除特别声明外,著作权归作者所有。转载请注明出处!

请我喝杯咖啡吧~