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