1.两数之和

Author Avatar
道路上奋斗的人儿 6月 30, 2021

1.两数之和(来源LeetCode)

给定一个整数数组 nums 和一个整数目标值 target,请你在该数组中找出 和为目标值 target 的那 两个 整数,并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是,数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。

示例 1:

1
2
3
输入:nums = [2,7,11,15], target = 9
输出:[0,1]
解释:因为 nums[0] + nums[1] == 9 ,返回 [0, 1] 。

示例 2:

1
2
输入:nums = [3,2,4], target = 6
输出:[1,2]

示例 3:

1
2
输入:nums = [3,3], target = 6
输出:[0,1]

1、暴力解法

第一眼看上去就想着暴力解决,直接两层for。

1
2
3
4
5
6
7
for ($i = 0; $i < count($nums);$i++) {
for ($j = 0; $j < count($nums); $j++) {
if (($nums[$i] + $nums[$j] == $target)) {
return array($i, $j);
}
}
}

然而运行第二个示例的时候发现了暴力解的问题。

存在重复值的情况,我看部分评论区多个解法的,可能没有这个。

1
2
3
4
5
6
7
for ($i = 0; $i < count($nums);$i++) {
for ($j = 0; $j < count($nums); $j++) {
if (($nums[$i] + $nums[$j] == $target) && ($i != $j)) {
return array($i, $j);
}
}
}

加上一个判等就行了。

2、其他解法

根据github->leetcode-matser的解答,自己突然想到时间复杂度为O(n)的解决办法。

1
2
3
4
5
6
7
8
9
10
11
12
13
function twoSum(array $nums, int $target): array
{
for ($i = 0; $i < count($nums);$i++) {
// 计算剩下的数
$residue = $target - $nums[$i];
// 匹配的index,有则返回index, 无则返回false
$match_index = array_search($residue, $nums);
if ($match_index !== false && $match_index != $i) {
return array($i, $match_index);
}
}
return [];
}

但后面查了下他们所说的,array_search 好像是效率比array_flip低。

相关内容:https://www.php.cn/php-weizijiaocheng-432375.html

于是乎自己又尝试写了下array_flip版,但是时间更加长了。

array_flip 版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function twoSum(array $nums, int $target): array
{
for ($i = 0; $i < count($nums);$i++) {
// 计算剩下的数
$residue = $target - $nums[$i];
// 匹配的index,有则返回index, 无则返回false
$reverse_nums = array_flip($nums);
$is_exist = array_key_exists($residue, $reverse_nums);
if ($is_exist !== false && $reverse_nums[$residue] != $i) {
return array($i, $reverse_nums[$residue]);
}
}
return [];
}

然后自己又去看了code上其他的解法,发现其实跟这个原理差不多,但是时间比这个快了贼多,就很迷。

其他版代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function twoSum(array $nums, int $target): array
{
$keyMap = [];
foreach ($nums as $key => $num) {
$keyMap[$num] = $key;
}
$length = count($nums);
for ($i = 0; $i < $length; $i++) {
$diff = $target - $nums[$i];
if (isset($keyMap[$diff]) && $i != $keyMap[$diff]) {
return [$i, $keyMap[$diff]];
}
}
return [0, 0];
}

自己的三次时间对比(反序)

版权声明:本文为博主原创文章,遵循[ CC 4.0 BY-SA ]版权协议,转载请附上原文出处链接和本声明。
本文链接:http://wbscr.cn/2021/06/30/1-liang-shu-zhi-he/