リートコードの問題を解く log-1.

整数の配列 nums とターゲットが与えられたとき、その和がターゲットとなる配列内の 2 つの整数を求め、それらの配列添え字を返します。

各入力は1つの答えにしか対応しないと仮定できます。ただし、配列の同じ要素を 2 回使用することはできません。

問題解決のアイデア

時間に対して空間を使い、1回トラバースすることで答えを見つけます。まずハッシュ表を作ります。各要素をトラバースしながら、2つのことを行います：

1. キーは現在の要素の値で、値はハッシュテーブルに追加された現在の添え字です。
2. n 番目の要素までトラバースすると、ハッシュ・テーブルに移動し、対象となる値 nums[n] を検索します。ルックアップが成功した場合、現在の値の添え字と、ハッシュ・テーブルで見つかった値が答えとなります。見つからなければ、トラバースを続行します。

最悪のシナリオは、答えを見つける前にデータ全体を走査することです。ハッシュテーブルのルックアップの複雑さはO(1)なので、アルゴリズム全体の複雑さはO(n)です。

code

• python3

class Solution:
 def twoSum(self, nums: List[int], target: int) -> List[int]:
 pass_index_map = dict()
 for index, value in enumerate(nums):
 if pass_index_map.get(target-value) is not None:
 return [pass_index_map.get(target-value), index]
 pass_index_map[value] = index
 return [None, None]

• Go

func twoSum(nums []int, target int) []int {
 passedIndexMap := make(map[int]int)
	for index := 0; index < len(nums); index++ {
		r := target - nums[index]
		lastIndex, ok := passedIndexMap[r]
		if ok {
			return []int{lastIndex, index}
		}
		passedIndexMap[nums[index]] = index
	}
	return []int{1, 2} 
}