LeetCode 1. Two Sum (PHP)

不知道吃錯什麼藥，突然上進了起來，竟然來刷題！目前程度很普通，先挑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 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: 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]

Constraints:

2 <= nums.length <= 10⁴
-10⁹ <= nums[i] <= 10⁹
-10⁹ <= target <= 10⁹
Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than O(n²) time complexity?

解題

這題我直接用暴力解法 (/ω＼)

題目很好懂，給訂一個陣列，找出不重複的兩個值，相加等於給定值。

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $cal = [];
        foreach ($nums as $key1 => $val1) {
            foreach ($nums as $key2 => $val2) {
                if ($key1 == $key2) continue;
                else if($target - $val1 == $val2) {
                    $cal[] = $key1;
                    $cal[] = $key2;
                    break 2;
                }
            }
        }
        
        return $cal;
    }
}

Runtime: 2335 ms, faster than 14.53% of PHP online submissions for Two Sum.

Memory Usage: 16.2 MB, less than 97.47% of PHP online submissions for Two Sum.

進階

果然跑兩個迴圈執行時間會很久，參考網路上大神寫的，執行速度差超級多！又長知識了🤓

class Solution {

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

Runtime: 270 ms, faster than 56.82% of PHP online submissions for Two Sum.

Memory Usage: 16.2 MB, less than 97.47% of PHP online submissions for Two Sum.

看到才56.82%不死心，又繼續測試了一下！！有差有差

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $map = [];
        for ($i=0;$i<=count($nums);$i++) {
            $diff = $target - $nums[$i];

            if (array_key_exists($diff, $map)) {
                return [$map[$diff], $i];
            } else {
                $map[$nums[$i]] = $i;
            }
        }
        return [];
    }
}

Runtime: 28 ms, faster than 70.92% of PHP online submissions for Two Sum.

Memory Usage: 16.6 MB, less than 27.48% of PHP online submissions for Two Sum.