目次

No.	項目
1	概要
2	問題
3	解法
4	ハッシュマップを使った解法（本当はこっちが正答）

概要

●発端
　・競プロ初心者、コーディング面接でズタボロにされ、
　・最低限のアルゴリズム学習とコーディング力強化を習慣化するため記事化
●環境
　・LeetCodeブラウザ上で実装（vscodeに拡張機能にするかもシレナイ）
　・言語はpython3
●その他ルール
　・google検索は自由に（直接的なLeetCodeの問題解説ページはNG）
　　（60分実装して実装出来なければ解説ページ参照）
　・コーディング面接対策のために解きたいLeetCode 60問から問題選出
　・「1000000」は任意の2進数とする

問題

1. Two Sum

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.

⇨配列numsと整数targetが渡されるよ。
　numsの中の要素２つを足すとtargetになる組み合わせが１パターンだけあるよ。
　足す要素は同じ要素を２回使っちゃだめだよ。
　足してもtargetになる組み合わせは必ずあるよ。
　正しい組み合わせの要素インデックスを返してネ。
　　という具合のことが書かれています。知らんけど。

ex Input: nums = [2,7,11,15], target = 9 Output: [0,1] 補足：nums[0]とnums[1]に入っている要素2と7を足すと9になる

※正答のないテストはInvalid Testcaseで弾かれるので考慮不要
　（ex. Input: nums = [2,7,11,15], target = 30)
※正答が複数あるテストもInvalid Testcaseで弾かれるので考慮不要
　Input: nums = [2,7,4,5], target = 9

解法

実施時間：35分

要素が重ならないように2重ループして総当たりで判定していけばOK

コーディング前の仮コーディングはこんな感じ

        #要素LOOP A　最初~最後
            #要素LOOP B　2つ目~最後
            #AとB照合
                #Trueならreturn
        #LOOP終了したらFalse

実際のsubmitコードはこちら

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        secoundNums = list(nums)
        for i,firstNum in enumerate(nums):
            secoundNums.pop(0)
            for j,secoundNum in enumerate(secoundNums):
                if firstNum + secoundNum == target:
                    return [i,j+i+1]
        return False

注意点は
　pythonの代入は参照型なので、2つ目のループ宣言時にはlist()で参照回避すること
　pop(0)は破壊的なので、jの要素数が実際よりi周回分マイナスになるため要調整
　~~↑可読性ゴミ~~

ハッシュマップを使った解法（本当はこっちが正答）

正直BigOとかふんわりしか分かってない自分でもわかる。これは力技や（確信）

どうやら私のコードは時間計算量がO(n2)なのが難点のよう。

LeetCode / Two Sum」

↑こちらで辞書（ハッシュテーブル）を使用した解法がされていました。
とりあえず「二重for文ぶん回し解法」と「全部辞書にしまっちゃう解法」で比較してみました。

↑二重for文ぶん回し解法

↑全部辞書にしまっちゃう解法

ですよね〜。空間計算量がO(n)に増しても、
時間計算量がO(n)になればこうなりますよね（分かってない）

備忘：BigOも一度ちゃんと学習