1. Two Sum

題目大意

給定一個整數陣列 nums 和一個整數 target，返回兩個數的索引，使它們相加等於 target。 你可以假設每個輸入都恰好有一個解，並且你不能重覆使用相同的元素。 你可以以任何順序返回答案。

題目原文連結

範例一

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

範例二

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

約束條件

• 2 <= nums.length <= 104
• 109 <= nums[i] <= 109
• 109 <= target <= 109 只存在一個有效答案。

  追加問題: 能否想出一個時間覆雜度低於O(n2)的算法？

解題想法

• 期望nums[i] +nums [j] = target，所以target - nums[i] = nums[j] 或 target-nums[j] = nums[i]
• 每次遍歷迴圈時，檢查 target 與當前元素的差值是否已經在陣列中，如果這個差值存在，就代表就找到了一對數，返回這兩個數的索引。

自己的答案

<?php
class Solution {
    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $len = count($nums);
        $map =[];
        for ($i = 0;$i<$len;$i++) {
            $diff = $target - $nums[$i];
            if (array_key_exists($diff, $map)) {
                return [$map[$diff], $i];
            } else {
                $map[$nums[$i]] = $i;
            }
        }
        return [];
    }
}