アルゴリズムの復習：2つの数の和

トピック分析

各入力は1つの答えにしか対応しないと仮定できます。しかし、この配列の同じ要素を何度も再利用することはできません。

例

与えられた数= [2, 7, 11, 15], target = 9
なぜなら[0] + nums[1] = 2 + 7 = 9
では、戻る[0, 1]

トピック分析

まず、問題を見れば、すぐに乱暴な解法が思いつきます。各要素xを繰り返し処理し、target - xに等しい値を持つtarget要素が存在するかどうかを調べる」だけです。

この解決法は単純すぎるので、そのままコードに進みます：

func twoSum(nums []int, target int) []int {
	for i, v := range nums {
		for k := i + 1; k < len(nums); k++ {
			if target-v == nums[k] {
				return []int{i, k}
			}
		}
	}
	return []int{}
}

実施結果：

実行は成功しましたが、その解の時間複雑度はO(n²)と高すぎました。実行時間の複雑さを最適化するためには、配列中の対象要素の存在をチェックする、より効率的な方法が必要です。空間と時間を交換することで、ハッシュテーブルを使用することが考えられます。

問題 イラスト

nums = [2, 7, 11, 15]、target = 9 とします。

<1> まず最初に、i を現在の添え字として、配列 nums を反復処理します。各トラバース値をキーとしてマップに入れる必要があります。

<2> 同時に、それぞれの値について、 target-nums[i] のキー値がマップに存在するかどうかを判断します。この場合、9-7=2となり、2がすでにマップに存在していることがわかります。

<3> つまり、2 と 7 があるキーに対応する値、つまり [0,1] です。は、探している 2 つの配列の添え字です。

Go言語の例

以上の分析に基づき、次のような解が得られます：

func twoSum(nums []int, target int) []int {
 result := []int{}
 m := make(map[int]int)
 for i,k := range nums { 
 if value,exist := m[target-k];exist {
 result = append(result,value)
 result = append(result,i)
 }
 m[k] = i
 }
 return result
}

実施結果：

私が書いたすべての解答と各問題の完全な図解をeBookにまとめました。