More than 3 years have passed since last update.

LeetCode 1000000本ノック【1. Two Sum】

Posted at 2021-05-04

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