[LeetCode]Two Sum

Two Sum 

給一串整數陣列為 nums 和一個整數 target，需要回傳兩個加總起來等於 target 的兩個索引值。

輸入的陣列一定只會有一個解，且索引值不能重複使用。

Example 1

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

Example 2

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

Example 3

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

解法

暴力解法

利用兩層for迴圈進行計算，以 [2, 7, 11, 15] 為例，(2, 7)、(2, 11)、(2, 15)、(7, 11)...以此類推，當加總等於目標值即回傳結果。

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];
        }
    }
}

雜湊解法

將目標值與當前數值相減後比對雜湊表，並把當前的 value-key 存放到雜湊表，重複此操作直到找到結果。

nums = (11, 7, 2, 15)

target = 9

current_key: 0,

current_num: 11,

remaining: -2

map: {11:0},

return: null

current_key: 1,

current_num: 7,

remaining: 2

map: {11:0, 7:1},

return: null

current_key: 2,

current_num: 2,

remaining: 7

map: {11:0, 7:1},

return: [2, 1]

PHP

function twoSum($nums, $target)
{
    $map = [];

    foreach ($nums as $key => $number) {
        $remaining = $target - $number;
        if (isset($map[$remaining])) {
            return [$key, $map[$remaining]];
        }

        $map[$number] = $key;
    }
}

Python

def twoSum(self, nums: list, target: int):
    map = {}

    for key in range(len(nums)):
        remaining = target - nums[key]
        if map.get(remaining) != None:
            return [key, map.get(remaining)]
        map[nums[key]] = key