題目：給定一個整數數組 nums 和一個目标值 target，請你在該數組中找出和為目标值的那 兩個 整數，并傳回他們的數組下标。
說明：你可以假設每種輸入隻會對應一個答案。但是，你不能重複利用這個數組中同樣的元素。
示例：
給定 nums = [2, 7, 11, 15]，target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
是以傳回 [0, 1]
解法一：暴力法
思路分析：
暴力法很簡單，周遊每個元素 x，并查找是否存在一個值與 target−x 相等的目标元素 PHP代碼實作：
/**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
for($i=0;$i<count($nums);$i++){
for($j=$i+1;$j<count($nums);$j++){
if($nums[$i] + $nums[$j] == $target){
return [$i,$j];
}
}
}
} 複雜度分析：
時間複雜度：O(n^2)
對于每個元素，我們試圖通過周遊數組的其餘部分來尋找它所對應的目标元素，這将耗費 O(n) 的時間
空間複雜度：O(1) 解法二：兩遍哈希表
為了對運作時間複雜度進行優化，我們需要一種更有效的方法來檢查數組中是否存在目标元素。如果存在，我們需要找出它的索引。保持數組中的每個元素與其索引互相對應的最好方法是什麼？哈希表（hashTable）。
通過以空間換取速度的方式，我們可以将查找時間從 O(n) 降低到 O(1)。哈希表正是為此目的而建構的，它支援以 近似 恒定的時間進行快速查找。我用“近似”來描述，是因為一旦出現沖突，查找用時可能會退化到 O(n)。但隻要你仔細地挑選哈希函數，在哈希表中進行查找的用時應當被攤銷為 O(1)。
一個簡單的實作使用了兩次疊代。在第一次疊代中，我們将每個元素的值和它的索引添加到表中。然後，在第二次疊代中，我們将檢查每個元素所對應的目标元素（target - nums[i]）是否存在于表中。注意，該目标元素不能是 nums[i] 本身！
采用數組函數 `array_keys()` 來解題， 傳回包含數組中所有鍵名的一個新數組
`array_keys()` 是一個哈希函數 /**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
for($i=0;$i<count($nums);$i++){
$difNum = $target - $nums[$i];
$keys = array_keys($nums,$difNum);
foreach($keys as $key){
if($key && $key != $i){
return [$i,$key];
}
}
}
} 時間複雜度：O(n)
我們把包含有 n 個元素的清單周遊兩次。由于哈希表将查找時間縮短到 O(1) ，是以時間複雜度為 O(n)
空間複雜度：O(n)
所需的額外空間取決于哈希表中存儲的元素數量，該表中存儲了 n個元素 解法三：一遍哈希表
思路1：array_keys_exists()
事實證明，我們可以一次完成。在進行疊代并将元素插入到表中的同時，我們還會回過頭來檢查表中是否已經存在目前元素所對應的目标元素。如果它存在，那我們已經找到了對應解，并立即将其傳回。
采用數組函數 `array_key_exists()` 來解題， 判斷數組是否存在此鍵名
`array_key_exists()` 是一個哈希函數 /**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
$find = [];
for($i=0;$i<count($nums);$i++){
$difNum = $target - $nums[$i];
if(array_key_exists($difNum,$find)){
return [$find[$difNum],$i];
}
$find[$nums[$i]] = $i;
}
} 時間複雜度：O(n)
我們隻周遊了包含有 n個元素的清單一次。在表中進行的每次查找隻花費 O(1)的時間
空間複雜度：O(n)
所需的額外空間取決于哈希表中存儲的元素數量，該表最多需要存儲 n個元素 思路2：使用isset()代替array_key_exists()
`isset()`性能比`array_key_exists()`要好，因為`isset()`是語言結構，而`array_key_exists()`是函數，語言結構的解析運作要比函數快一點。 /**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
$find = [];
for($i=0;$i<count($nums);$i++){
$difNum = $target - $nums[$i];
if(isset($find[$difNum])){
return [$find[$difNum],$i];
}
$find[$nums[$i]] = $i;
}
} 時間複雜度：O(n)
空間複雜度：O(n) 小貼士：
* isset()效率高于array_key_exists(), PHP7之後有30%左右的提升, php5.6有将近70%的提升
* isset()是文法結構, array_key_exists()是函數, 調用開銷要小
* isset()通過 Z_TYPE_P 擷取變量類型，然後再進行判斷實作的; array_key_exists()則是通過hash查找來實作的
* 對于數組，isset()的性能要高于array_key_exists() 是以，如果數組比較大，我們應該用如下方法保證性能和準确性 isset() 解法四：二分查找法
用一個排序都能把複雜度降到 O(nlogn)，通過排序，然後用兩個指針從前後掃描逼近真值。
注意這個思想，可以讓 O(n^2) 的複雜度降為 O(n)，充分利用排序，因為一定會有一個值滿足，然後通過值去原數組裡找對應的下标。
前提，該數組已經是一個有序數組，必須先排序，再查找 /**
* @param Integer[] $nums
* @param Integer $target
* @return Integer[]
*/
function twoSum($nums, $target) {
$origin = $nums;
sort($nums);
$left = 0;
$right = count($nums) - 1;
while($left <= $right){
if($nums[$left] + $nums[$right] == $target){
$start = array_keys($origin,$nums[$left]);
$end = array_keys($origin,$nums[$right]);
return [reset($start),end($end)];
}elseif($nums[$left] + $nums[$right] > $target){
$right -= 1;
}elseif($nums[$left] + $nums[$right] < $target){
$left += 1;
}
}
} 時間複雜度：O(logn)
空間複雜度：O(1) 四種解法的性能對比
時間複雜度：
Ο(1)＜Ο(log2n)＜Ο(n)＜Ο(nlog2n)＜O(n^2)＜O(n^3)＜…＜Ο(2n)＜Ο(n!) 結論：
一般算法是否最優，主要看時間複雜度，往往最優的算法需要犧牲空間複雜度
一遍哈希表 < 二分查找法 < 兩遍哈希表 < 暴力法 github
LeetCode_PHP：https://github.com/zhangdejian/LeetCode_PHP
後記
自己隻能解出第一和第二種思路，原來還有其它思路解，soga，漲知識了。
自己不屬于那種最聰明的或最有天賦的人，隻能後天靠努力來補啦哈，反正多刷刷算法題，準沒錯，可以讓自己的思維和深度無限延伸。
題目來源：力扣（LeetCode）
連結：
https://leetcode-cn.com/problems/two-sum