# 前言

藉由 LeetCode 磨練演算法

# 題目連結

Two Sum - LeetCode

# 解題思路

# 暴力解

跑兩層 loop，逐一比較，直到找到兩個 item 相加等同 target

時間複雜度

時間複雜度為 O(n²)

空間複雜度

由於會在每一次 loop 當中直接比較兩個 item，所以不需維護特定 variable，空間複雜度為 O(1)

# Hash Table

可以使用 dictionary 的方式來解，將 $target — $item = $diff，再把 $diff 放到 dictionary 中，這樣下次 loop 的 item 如果與 $diff 相加等於 $target，那就得到答案

solution code

<?php
class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $dic = [];
        $len = count($nums);

        for ($i = 0; $i < $len; $i++) {
            if (isset($dic[$nums[$i]])) {
                return [$i, $dic[$nums[$i]]];
            }

            $diff = $target - $nums[$i];
            $dic[$diff] = $i;
        }

    }
}

時間複雜度

只跑一層 loop，所以時間複雜度為 O(n)

空間複雜度 $dic 會隨著 n 而增加，所以空間複雜度為 O(n)