【LeetCode】1.Two Sum両数の和(Python)

目次

1. タイトル

2. 解答

2.1誤答(自己の)

2.2正解(他人の)

2.3対比

1.テーマ
整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、その配列の下付きを返します.入力ごとに1つの答えしか対応しないと仮定できます.しかし、この配列の同じ要素を繰り返し利用することはできません.例:nums=[2,7,11,15]が与えられ、target=9はnums[0]+nums[1]=2+7=9であるため[0,1]を返す
注意問題で返されるのは配列の下付きです.

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """

2.解答
最も考えやすいのは暴力解法で、明らかに実行できるが必要ない.
2.1誤答(自己)

まず、タイトルは下付き文字を返すことを要求するので、保存数の対応する下付き文字を保存し、Pythonでは辞書を使って下付き文字を保存する操作を行う.辞書形式は「数:下付き」

次に、配列をソートした後、ヘッダポインタを設定し、ヘッダポインタとtargetより大きい場合、ヘッダポインタを左にシフトさせることができると考えられる.和がtarget未満の場合、ヘッダポインタは右に移動します.和がtargetに等しい場合は、対応する2つの数が見つかり、辞書に対応する下付き文字が見つかり、結果が返されます.考えはコードを回して、内心は

喜びます

class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if len(nums) < 2:
            return None
        d = {}
        for i in xrange(len(nums)):
            d[nums[i]] = i
        nums.sort()
        left = 0
        right = len(nums) - 1
        two = nums[left] + nums[right]
        while left < right and two != target:
            if two < target:
                left += 1
            else:
                right -= 1
            two = nums[left] + nums[right] 
        return [d[nums[left]], d[nums[right]]]

実行エラーnums=[3,3]の場合、上記のコードに従って[1,1]が返されます.配列に同じ要素が存在する場合は無視されます.

2.2正解(他人の)
以下の考え方は,他人の正しいコードに基づいて考え方を復唱する.他の人が誰なのか、私も知らない、LeetCodeの上の

まず,テーマは配列の下付き文字を返すことを要求するので,数の対応する下付き文字を保存すべきであり,Pythonでは辞書を用いて下付き文字を保存する操作を行う.字典の形式は“数:下标”です(私のこの考え方は正しい窃喜√)

配列を順次巡回し、「target-現在数」が辞書にある場合、対応する2つの数を見つけ、現在の下付き文字を返し、辞書に「target-現在数」に対応する下付き文字を見つける.「target-現在数」が辞書にない場合は、「現在数:現在数の下付き」を辞書に保存します.

class Solution(object):
   def twoSum(self, nums, target):
       """
       :type nums: List[int]
       :type target: int
       :rtype: List[int]
       """
       d = {}
       for i in xrange(len(nums)):
           other = target - nums[i]
           if other in d:
               left = d[other]
               right = i
               return [left, right]
           d[nums[i]] = i
       return None

2.3比較
複雑に考えないでください、実はとても簡単で、正しいことまで1つだけなくして、このなくして菜鳥と大物の差8博文は記録用で、伝言の交流を歓迎します.