LeetCode: 1. Two Sum (Easy) by PHP

はじめに

LeetCodeの「1. Two Sum」の個人的な考察です。
解いてから模範解答を見て書いています。
言語はPHPです。

問題

解法

1. Blute Force (総当たり)

<?php

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $count = count($nums);
        for ($i = 0; $i < $count; $i++) { 
            for ($j = $i + 1; $j < $count; $j++) {
                if ($nums[$i] + $nums[$j] === $target) {
                    return [$i, $j];
                } 
            }
        }
        return [];
    }
}

普通に考えたらこうでした。
配列内の2つの要素を足し合わせたらtargetの数字になると。

ただしTime complexity (時間計算量)がO(n²)でよくありません。
見るからにループが入れ子になっていますしね…。

$j = $i + 1しているのは、一度チェックした数字を見ないようにするための工夫ですが、焼け石に水です。

2. Two-pass Hash Table

[2, 5, 6, 7]でtargetは9みたいなケースだと、2に対するペアである7を探せば答えが出ます。
しかし配列の要素であるため、すぐに探せない。そこで…。

<?php

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $inums = array_flip($nums);
        $count = count($nums);
        for ($i = 0; $i < $count; $i++) {
            $searchNum = $target - $nums[$i]; 
            if (isset($inums[$searchNum]) && $inums[$searchNum] !== $i) {
                return [$i, $inums[$searchNum]];
            }
        }
        return [];
    }
}

PHPにはarray_flip関数があるので、キーと値をひっくり返すことが簡単にできます。
上記の例でいうと、2のペアである7を探しに行くのですが、例えば[2, 3, 5, 3]みたいなケースでは[1, 1]が成り立ってしまうので、それは避けるべくif文に$inums[$searchNum] !== $iを追加しています。

3. One-pass Hash Table

結果はかなり良くなりますが、とはいえまだarray_flipで内部的にはループしていることになります。

なのでチェックするループ内に後置的に値をセットしていくのが今回のやり方です。
ただし後置的に反転した配列を作成していくので、returnするタイミングは一歩遅くなることになります。

しかし後置的にすることで[2, 3, 5, 3]の場合に1のときに自分を拾う必要がなくなります。
また1, 2番目と比べて結果の配列の1つ目と2つ目が逆になります。

PHPの配列は連想配列（ハッシュ、マップ）なので、[1, 3]と[3, 1]が一緒と言われてもピンと来ないかもしれませんが…。

その場合は、returnの配列の順番を書き換えても問題ないでしょう。
（下記は公式の解答に準拠してます）

<?php

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer[]
     */
    function twoSum($nums, $target) {
        $count = count($nums);
        for ($i = 0; $i < $count; $i++) {
            $searchNum = $target - $nums[$i]; 
            if (isset($inums[$searchNum])) {
                return [$i, $inums[$searchNum]];
            }
            $inums[$nums[$i]] = $i;
        }
        return [];
    }
}

終わりに

自分なりの学習メモを残していこうと思って書いた記事です。
しばらく試行錯誤が続きそう…。

2つ目はまだしも、3つ目は思いつかなさそう。PHP的にはarray_flipが先に頭に浮かびそうで、自前で作っていく発想にいたらなさそうだなと思った次第です。

2つ目も、forの入れ子を脱するやり方を思いつけるか…。

HRR Co., Ltd.

技術的な記録を残していくことを目的としています。1次情報を大事にしています。