leetcode——二数の和

に質問
整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、その配列の下付きを返します.入力ごとに1つの答えしか対応しないと仮定できます.しかし、この配列の同じ要素を繰り返し利用することはできません.
例:

   nums = [2, 7, 11, 15], target = 9

   nums[0] + nums[1] = 2 + 7 = 9
     [0, 1]

構想過程.
初めてLeetCodeに触れて、この問題は本当に簡単だと感じました.この配列を2回遍歴して、和を求めればこの問題を解決することができます.

class Solution(object):
    def twoSum(self, nums, target):
        for i, x in enumerate(nums):
            for j, y in enumerate(nums):
                if i == j:
                    pass
                else:
                    if x+y == target:
                        return i, j

提出後、解答がタイムアウトしたことに気づき、その時、本当に考え始め、効率を高めるにはどうすればいいかを考え始めました.
上のコードは明らかで、毎回i==jを追加判断して、この判定を少し修正します.

class Solution(object):
    def twoSum(self, nums, target):
        for i, x in enumerate(nums):
            for j, y in enumerate(nums):
                if x+y == target:
                    if i != j:
                        return i, j

このように簡単に修正してみると、提出が通過し、問題を解くのに4000+ms時間がかかり、さらに大きな向上の余地があるようだ.hash を巡回する効率は を巡回する効率よりも高いので、2回目の をhash に変更することができます.

class Solution(object):
    def twoSum(self, nums, target):
        dicts = {}
        for i, x in enumerate(nums):
            dicts[x] = i
        for i, x in enumerate(nums):
            if (target-x) in dicts:
                if i != dicts[(target-x)]:
                    return i, dicts[target-x]

以上,コード構造や考え方は変化せず, をhash に置き換えただけであるが,解題時間は4000+msから58msに短縮された.
締めくくり
初めてLeetCodeに接触して、突然これらの問題が終わったことを発見して、私たちが普段コードを書く習慣を最適化することができます.