用 PHP 解 LeetCode 系列，這次是經典題目 Two Sum，屬於 Easy

原始題目

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.

Example:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Input: nums = [3,2,4], target = 6
Output: [1,2]

Input: nums = [3,3], target = 6
Output: [0,1]

題目分析

1. 輸入一個還有多個數字的陣列，以及預期數字
2. 找出陣列中兩數和等於預期數字的值，並用陣列方式回傳兩個數字在陣列中的鍵值

解題過程

直覺的暴力解是兩個迴圈嵌套，類似九九乘法的做法。但是這麼做時間複雜度會很高
並且內層迴圈會重複遍歷當前鍵值的數字，每次外層迴圈都要先建立新的內層陣列物件才能比對
對記憶體使用也會增加

最終使用一次迴圈的解決方案
遍歷傳入的陣列，比對 target 減掉當前數字的差值是否存在陣列剩餘的數字中
為什麼說是 剩餘 的數字中呢？先看完程式碼再繼續說明

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        foreach ($nums as $k1 => $v1) {
            unset($nums[$k1]);
            if ($k2 = array_search($target - $v1, $nums)) {
                return [$k1, $k2];
            }
        }
        return [];
    }
}

如果不使用 unset 永久把數字從陣列排除掉

unset($nums[$k1]);

在輸入 inpout = [3, 3], target = 6，預期結果為 [0, 1] 的時候
會因為 array_search 在查詢值等於 3 (6 - 3) 的數字的時候，因為第一個數字就是 3
而造成 $k2 = 0 而輸出 [0, 0]！