Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
2
Help us understand the problem. What is going on with this article?
@nazekaugoku

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

目次

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

概要

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

問題

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の中の要素2つを足すとtargetになる組み合わせが1パターンだけあるよ。
 足す要素は同じ要素を2回使っちゃだめだよ。
 足しても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文ぶん回し解法」と「全部辞書にしまっちゃう解法」で比較してみました。

image.png

↑二重for文ぶん回し解法

image.png

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

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

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

2
Help us understand the problem. What is going on with this article?
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away

Comments

No comments
Sign up for free and join this conversation.
Sign Up
If you already have a Qiita account Login
2
Help us understand the problem. What is going on with this article?