# 前言

藉由 LeetCode 來磨練演算法

# 題目連結

Intersection of Two Arrays - LeetCode

# 解題思路

# 暴力解

使用兩層 for loop 來解

solution code:

<?php
class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersection($nums1, $nums2) {
        $nums1Len = count($nums1);
        $nums2Len = count($nums2);
        $res = [];
        $occured = [];
        for ($i = 0; $i < $nums1Len; $i++) {
            for ($j = 0; $j < $nums2Len; $j++) {
                if ($nums1[$i] === $nums2[$j] && !isset($occured[$nums2[$j]])) {
                    $occured[$nums2[$j]] = true;
                    $res[] = $nums2[$j];
                }    
            }
        }

        return $res;
    }
}

時間複雜度為 O(N²) 空間複雜度為 O(N)

# 使用 dictionary

把 $nums1 or $nums2 選一個轉成 dictionary，以減少時間複雜度

solution code:

<?php
class Solution {

    /**
     * @param Integer[] $nums1
     * @param Integer[] $nums2
     * @return Integer[]
     */
    function intersection($nums1, $nums2) {
        $nums1Map = [];
        $nums1Len = count($nums1);
        $nums2Len = count($nums2);
        $res = [];

        for ($i = 0; $i < $nums1Len; $i++) {
            $nums1Map[$nums1[$i]] = true;
        }

        for ($i = 0; $i < $nums2Len; $i++) {
            if (($nums1Map[$nums2[$i]]) === true) {
                $res[] = $nums2[$i];
                $nums1Map[$nums2[$i]] = false;
            }
        }

        return $res;
    }
}

時間複雜度為 O(N)

空間複雜度為 O(N)