2つの数の和

質問する
1つの配列の2つの数値インデックスを返し、加算によってターゲットを作成できます.

入力

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

出力

[0, 1]

説明
nums[0] + nums[1] = 2 + 7 = 9
したがって、0と1を返します.

に答える
ブルートフォース
ブルトボス:どのようにすべての組み合わせを合わせて一つ一つ検査しますか?

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]

この場合,時間的複雑度はO(n**2)であり,速度が遅すぎる.
inを使用したナビゲーション
target−nに存在するかどうかを探索する問題となる.
inの時間複雑度はO(n)であるため,時間全体の複雑度は以前と同じであるが,同じ時間複雑度でもinの演算速度はずっと速い.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    for i, n in enumerate(nums):
        complement = target - n
            
        if complement in nums[i + 1:]:
            return nums.index(n), nums[i + 1:].index(complement) + (i + 1)

クエリー結果キー(最初のキーを除く)
ディックシャーナはハッシュテーブルで実現し,分割返済解析による時間複雑度はO(1),全体はO(n)であった.
キーと値を交換してdickshernerとして保存すると、キークエリターゲットから最初の数を減算した結果、すぐに正しい答えを見つけることができます.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map = {}
    # 키와 값을 바꿔서 딕셔너리로 저장
    for i, num in enumerate(nums):
        nums_map[num] = i
    
    # 타겟에서 첫 번째 수를 뺀 결과를 키로 조회
    for i, num in enumerate(nums):
        if target - num in nums_map and i != nums_map[target - num]:
            return nums.index(num), nums_map[target - num]

クエリー構造の改善
上記の性能に差はないが、コードをより簡潔にすることができる.

def twoSum(self, nums: List[int], target: int) -> List[int]:
    nums_map = {}
    # 하나의 for 문으로 통합
    for i, num in enumerate(nums):
        if target - num in nums_map:
            return [nums_map[target - num], i]
        nums_map[num] = i

ダブルポインタの使用
ダブルポインタ:左ポインタと右ポインタの合計がターゲットより大きい場合は、右ポインタが左に移動します.小さい場合は、左ポインタが右に移動して値を調整します.
二重ポインタの時間複雑度はO(n)であった.
結論から言えば、二重ポインタでは解けない.
numsがソートされず、ソートロジックが追加されている場合、インデックスはすべて破壊されるため、元のインデックスは見つかりません.
ソースコード