leetcode 01は2数の和Pythonバージョンを求めます

トピックの説明:整数配列numsとターゲット値targetを指定します.この配列でターゲット値の2つの整数を見つけて、それらの配列の下に返してください.
入力ごとに1つの答えしか対応しないと仮定できます.しかし、この配列の同じ要素を繰り返し利用することはできません.
例:
与えられたnums=[2,7,11,15],target=9
nums[0]+nums[1]=2+7=9なので[0,1]を返します
解法としては,第1の類似二分検索はまず第1の2数の和をtargetと比較し,targetより小さい場合はポインタhead+1,targetより大きい場合はポインタhead-1の時間複雑度はo(nlogn)である.

class Solution:
	def twoSum(self,nums,target):
		sorted_id=sorted(range(len(sum)),key=lambda k:num[k])
		head=0
		tail=len(nums)-1
		sum_result=num[sorted_id[head]]+num[sorted_id[tail]]
		while sorted_id!=target:
			if sorted_idtarget:
				tail-=1
			sum_result=num[sorted_id[head]]+num[sorted_id[tail]]
		rerurn [sorted_id[head],sorted_id[head]]

第2の解法:暴力法は所与のtargetに対して、配列時間複雑度O(n)を遍歴し、target==m+nの要素を検索し、時間複雑度O(n)は時間複雑度O(n^2)遍歴過程であるため、データ構造記憶を使用しないため、空間複雑度O(1)消費時間60 ms
直接ソートし、2つのポインタを作成し、まず最初のポインタを最初の数に、2番目のポインタは残りの数字(1サイクル)を巡ります.ループが終了すると、最初のポインタは2番目のビット数を指し、2番目のポインタは次に最初のポインタの後ろのすべての数を再遍歴します.順番にループして、必要な数値の和を見つけます.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        size = len(nums)
        for i, m in enumerate(nums):
            j = i + 1
            while j < size:
                if target == (m + nums[j]):
                    return [i, j]
                else:
                    # print(i, j, m + _n, " didn't match!")
                    j += 1

3つ目の方法:hash#を辞書でシミュレートして空の辞書を作成する最初のループはnums数値をkey、indexをvaluesとする辞書を生成することです.dict第2サイクルはtarget−m値の多さに対応するラベルjを導出し,最後に出力する.時間複雑度O(n)空間複雑度O(n)実行時間52 ms

  class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        _dict={}
        for i,m in enumerate(nums):
    	    _dict[m]=i
        for i,m in enumerate(nums):
            j=_dict.get(target-m)
            if j is not None and i!=j:
                return [i,j]

第四の方法:一次辞書シミュレーションHash#この方法は第三の方法の簡潔版であり、時間の複雑さと空間の複雑さも同様である.

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        _dict={}
        for i,m in enumerate(nums):
            if _dict.get(target-m) is not None:
                return [i,_dict.get(target-m)]
            _dict[m]=i

5つ目は2つのforサイクル時間の複雑さでn*n(最も単純で暴力的)
class Solution(object): def twoSum(self, nums, target): “”":type nums: List[int] :type target: int :rtype: List[int] “”"if not nums: return None dic = {} for i,key in enumerate(nums): tmp = target-key for item,value in dic.items(): if tmp == value: return [item,i] dic[i] = key return None