1.TwoSum.md

1st

２つの数の和がtargetになるようなインデックスを返す。 計算量O(n2)より早いアルゴリズムで実装するので以下のようなループ２回回す解法は不可。

＜解法１の私の回答＞

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        ans = []
        for i,firstNum in enumerate(nums):
            for j,secondNum in enumerate(nums):
                if i == j: continue
                if firstNum + secondNum == target: 
                    ans = [i,j]
                    break
            if ans != []: break
        return ans

ヒントを見た。ハッシュマップを使用するらしい。

例えば４つの配列があるときで考えてみる。[0,1,2,3] 総当たりの組み合わせはインデックスで表すと以下。 [0:1,0:2,0:3,1:2,1:3,2:3]

ここで5分経過。 解答を見る

まずbrute forceの解答も私の回答より少し洗練されていた。

＜解法１＞

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums)):
            for j in range(i + 1, len(nums)):
                if nums[j] == target - nums[i]:
                    return [i, j]
        # Return an empty list if no solution is found
        return []
#2つの for ループ

#外側のループ: for i in range(len(nums)):
#i を 0 から len(nums) - 1 まで動かす。
#内側のループ: for j in range(i + 1, len(nums)):
#j を i+1 から len(nums) - 1 まで動かす。

# i == jの時をループで考慮している。順列ではなく組み合わせ処理しているのでbreaksする必要がない。

Time complexity: O(n 
2
 ).
For each element, we try to find its complement by looping through the rest of the array which takes O(n) time. Therefore, the time complexity is O(n 
2
 ).

Space complexity: O(1).
The space required does not depend on the size of the input array, so only constant space is used.

解説を読むフェーズ

・ハッシュマップを使ってループを独立させるというのは実務でよく用いていましたので解答を読んだらすんなり理解できました。

・１回目に選ばれた数と２回目に選ばれた数の合計がtargetになるという認識にこだわり、抽象化したら解けるというアプローチにさえ気づけず、右往左往してしまった。

・問題の認識のプロセスを自分なりに振り返ってみると以下になる。反省点を踏まえて記載した。

target-num[i]が補数という定式化をしてその補数がリスト内にあれば良いという認識をできていなかった。この認識があれば、リスト内の値とインデックスをハッシュマップにキャッシュして、O(1)で取り出すという処理を思いつけたかもしれない。

・この時、変数を選択する時間の流れからハッシュマップを使用することにより疎にできるという視点で覚えておけば、抽象化という数学的な気づきがなくても、パターン認識的にハッシュマップを使用するというアプローチに至れるかもしれない。

・また、実例でループ中の変数と補数の組み合わせは考えていたが上記の発想に思い至らず実装はできなかった。O(n^2)の２回ループさせる解き方とは異なり、ハッシュマップ使用時は時間的に疎であり、必ずしも組み合わせの順序的に先にくるバリューで、組み合わせを考えて補数を見つける必要はないことはなんとなく理解できていた。(ループ２回回す時は、変数に対応する補数があることを前提としていたが、変数ではなくても変数の補数から組み合わせを見つけられれば問題ない）

・step1→step3に一足跳びに飛ぼうとしていたのもハッシュマップを用いて回答できなかったことの原因かもしれない。

・そもそもリストnumsのバリューをそのままループで回そうとしたところから間違っていた？ループを回してインデックスやバリューと関連付けを行うとき、２変数よりも１変数の方が思考がシンプルになるかも？

・一旦まとめると、1回目と２回目のバリューの選択を別々に考えていて関連付けができてなかった。ループの時間の流れという定数から疎になる方法を考えられなかった。ループすることにより何が得られるかについても漠然としていた。

・シンプルに考えつつ、制約を乗り越える回答を心がけたい。

2nd

・余裕と思っていたら条件分岐で詰まった。 ＜解法２の誤答＞

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}

        for i in range(len(nums)):
            num_to_index[nums[i]] = i
            print(num_to_index)

        for i in range(len(nums)):
            compliment = target - nums[i]
            print(compliment)

            if str(num_to_index[compliment]) in str(nums[i]) and compliment[nums[i]] == i:
                return [i, num_to_index[compliment]]

Runtime Error

KeyError: -2
           ~~~~~~~^^^^^^^^^^^^
    if str(hashmap[compliment]) in str(nums[i]) and compliment[nums[i]] == i:

Line 10 in twoSum (Solution.py)
          ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    ret = Solution().twoSum(param_1, param_2)

Line 41 in _driver (Solution.py)
    _driver()

Line 56 in <module> (Solution.py)

・２回目で解法2については1分程度でaccept

＜解法２＞

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}

        for i in range(len(nums)):
            num_to_index[nums[i]] = i

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in num_to_index and i != num_to_index[complement]:
                return [i, num_to_index[complement]]

        return []

・上記のループ回数を減らすことができる。ただし時間計算量は変わらない。 ・上記の解法２は最初のループで最後までループを回していて２回目のループで答えが見つかったら打ち切り、下記の解法３は答えが見つかったらループを打ち切るということをしている。 ・解法３の再現は5分以内で完了。その次の誤答との違いが分からなかったので、後ほど復習する。

＜解法３＞

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}

        for i in range(len(nums)):
            complement = target - nums[i]
            if complement in num_to_index:
                return [i, num_to_index[complement]]
            num_to_index[nums[i]] = i
        return []

＜解法３の誤答＞

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}

        for i in range(len(nums)):
            num_to_index[nums[i]] = i
            complement = target - nums[i]
            if complement in num_to_index:
                return [i, num_to_index[complement]]
        return []

誤答になる理由

多くの Two Sum 問題では、「同じ要素を 2 回使うのは不可」が前提です。そのため (1) のように

まずは、complement が “すでに辞書に登録されている（＝過去に見た要素）か” をチェック
なければ現在の要素を辞書に登録
という手順が定石です。
こうすることで「現在処理中の要素を自分自身のペアとして拾ってしまう」誤判定を防げます。

nodchip様の解説 [3, 3], target = 6 を渡すと [0, 0] が返ってきて誤答になる

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}

        for i in range(len(nums)):
            num_to_index[nums[i]] = i # ここで num_to_index = {3: 0} となる。
            complement = target - nums[i] # complement = 3
            if complement in num_to_index: # num_to_index = {3: 0} なので True になる。
                return [i, num_to_index[complement]] # [0, 0] が返る
        return []

3rd

時間をおいて（1ヶ月）復習も兼ねて。 1回目：7分48秒 詰まったところ ・pythoのリストの表記方法：List[int] ・for num in numsとしていて、求める答えをインデックスではなく数字の値としていた ・hashmapを使って検討済みの数字と順番を保存する発想

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}
        for i in range(len(nums)):
            compliment = target - nums[i]
            if compliment in num_to_index:
                return [num_to_index[compliment],i]
            num_to_index[nums[i]] = i
        return 

2回目:4分31秒

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        num_to_index = {}
        for i in range(len(nums)):
            compliment = target - nums[i]
            if compliment in num_to_index:
                return [num_to_index[compliment],i]        
            num_to_index[nums[i]] = i
        return []