1.2つの数の和python

整数配列とターゲット値を指定し、配列とターゲット値の2つの数を見つけます.入力ごとに1つの答えしか対応せず、同じ要素が再利用できないと仮定できます.
例:nums=[2,7,11,15]が与えられ、target=9はnums[0]+nums[1]=2+7=9であるため[0,1]を返す
問題解決の考え方:1,問題の意味に合致する配列要素の下付きを見つけるために,まず元の配列を深くコピーし,並べ替えなければならない.
2で、ソート後の配列に2つの数を探してtargetに加算します.この考え方は明らかである:2つのポインタ、1つのポインタ、1つのポインタは尾を指し、2つのポインタは中間に移動し、2つのポインタが指す数の和がtargetであるかどうかを検査する.この2つの数が見つかったら、この2つの数を元の配列の位置に見つければいいです.3、注意しなければならないのは、元の配列の中で下付き記号を探すときは、最初から探して、最後から探して、通過できないかどうかです.この例ではnumbers=[0,1,2,0];target=0.最初から探せば、問題があります.
以下は私が書いたものです.

class Solution:
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        n = len(nums)   #  nums   
        for x in range(0,n):
            a = target - nums(x)
            if a in nums:
                y = nums.index(a)
                if x == y:
                    continue
                else:
                    return x,y
                    break
            else:
                continue

大神解題:

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        index = []
        numtosort = num[:]; numtosort.sort()
        i = 0; j = len(numtosort) - 1
        while i < j:
            if numtosort[i] + numtosort[j] == target:
                for k in range(0,len(num)):
                    if num[k] == numtosort[i]:
                        index.append(k)
                        break
                for k in range(len(num)-1,-1,-1):
                    if num[k] == numtosort[j]:
                        index.append(k)
                        break
                index.sort()
                break
            elif numtosort[i] + numtosort[j] < target:
                i = i + 1
            elif numtosort[i] + numtosort[j] > target:
                j = j - 1

        return (index[0]+1,index[1]+1)

以上のコードは冗長すぎてdictつまりハッシュを使うと簡潔になります.

class Solution:
    # @return a tuple, (index1, index2)
    def twoSum(self, num, target):
        dict = {}
        for i in xrange(len(num)):
            x = num[i]
            if target-x in dict:
                return (dict[target-x]+1, i+1)
            dict[x] = i

別の構想コードの構想:このアルゴリズムの核心思想は辞書を構築することであり、辞書は現在の要素がtargetを完了するために必要な要素値をkeyとして格納し、現在の要素のindexをvalueとする.それから遍歴の過程の中で判断して、現在の要素は私の望む要素に属しているかどうか、そうであれば、直接[辞書の中のこの要素の下付き文字、現在の遍歴要素の下付き文字]を出力して考えます:このアルゴリズムはどこにありますか?時間的複雑度の観点から,第1層forループはO(n)であり,辞書はhash関数の構造を採用しているため,x in dictの検索過程において時間的複雑度はO(1)であるが,ここではindexクエリを用いずにvalue値を直接取得し,辞書のGet Itemの複雑度もO(1)であるため,アルゴリズム全体の時間的複雑度はO(n)であるが,ここでの空間的複雑度はO(n)であり,空間的に時間を変える.

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