首页 > > 网络编程 > Php编程 >

00 | Two Sum

2019-05-24 06:12:27来源：博客园阅读 ()

Question

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].

Answer

 1 class Solution {
 2 
 3     /**
 4      * @param Integer[] $nums
 5      * @param Integer $target
 6      * @return Integer[]
 7      */
 8     public function twoSum($nums, $target) {
 9         $res = [];
10         for($i=0; $i<count($nums); $i++) {
11             for($j=$i+1; $j<count($nums); $j++) {
12                 if($nums[$i]+$nums[$j] === $target) {
13                     array_push($res, $i);
14                     array_push($res, $j);
15                 } else {
16                     continue;
17                 }
18             }
19         }
20         return $res;
21     }
22 }

这是我想到的方案，the least efficient solution. ??

初步看下运行结果：

??‍♀?(捂脸...) But... facing it.

看了一下题解中，大神们的写法，受益匪浅，贴一下大神们的解法：

Solution One

 1 // solution 01
 2 class Solution
 3 {
 4     /**
 5      * @param Integer[] $nums
 6      * @param Integer $target
 7      * @return Integer[]
 8      */
 9     public function twoSum(array $nums, $target) 
10     {
11         $find = [];
12         $count = count($nums);
13         
14         for ($i = 0; $i < $count; $i++) {
15             $value = $nums[$i];
16             
17             if ($a = array_keys($find, ($target - $value))) {
18                 return [$a[0], $i];
19             }
20             
21             $find[$i] = $value;
22         }
23     }
24 }

该解法据说耗时64ms.

分析：

1. 遍历数组；
2. 将遍历过的元素按序存入新的变量Array $find中，判断($target - $value)这个值是否在$find中，如果在$find
  中，返回该值对应的键名$a[0]，这里也就是对应的索引值 以及 $i 表示的是 $nums 原数组的第几个元素。

Solution Two

 1 class Solution {
 2 
 3     /**
 4      * @param Integer[] $nums
 5      * @param Integer $target
 6      * @return Integer[]
 7      */
 8     function twoSum(array $nums, int $target) {
 9         $v = 0;
10         $map = [];
11         $len = count($nums);
12         for($i = 0; $i < $len; ++$i){
13             $v = $target - $nums[$i];
14             if(array_key_exists($v, $map) && $i != $map[$v])
15             {
16                 return [$map[$v] , $i];
17             }
18             $map[$nums[$i]] = $i;
19         }
20     }
21 }

这个据说耗时16ms... すごい ??!!!

分析：

这个和上面的其实比较类似

根据他们的解法，我自己又重新写了一个类似的版本，但是耗时在144ms左右，不过还是记录下来，以便日后查看：

Solution One By Cyan

 1 class Solution
 2 {
 3     /**
 4      * @param Integer[] $nums
 5      * @param Integer $target
 6      * @return Integer[]
 7      */
 8     public function twoSum(array $nums, $target) 
 9     {
10         $find = [];
11         $count = count($nums);
12         
13         for ($i = 0; $i < $count; $i++) {
14             $value = $nums[$i];
15             
16             if ($a = array_keys($nums, ($target - $value))) {
17                 if($a[0] !== $i) {
18                     return [$i, $a[0]];
19                 }
20             }
21         }
22     }
23 }

忽然想起 array_search ( mixed $needle , array $haystack [, bool $strict = FALSE ] ) 这个函数，又尝试了一下，大概是130ms多：

Solution Two By Cyan

 1 class Solution
 2 {
 3     /**
 4      * @param Integer[] $nums
 5      * @param Integer $target
 6      * @return Integer[]
 7      */
 8     public function twoSum(array $nums, $target) 
 9     {
10         $count = count($nums);
11         
12         for ($i = 0; $i < $count; $i++) {
13             $value = $nums[$i];
14             $diff = $target - $value;
15             $index = array_search($diff, $nums);
16             if($index !== false && $index !== $i) {
17                 return [$i, $index];
18             }
19         }
20     }
21 }