twoSum
時間計算量を減らすためにmapを使うことがキモ。
自分のコード
code:go
type idx = int
func twoSum(nums []int, target int) []int {
numAndIndices := mapidx[]idx{} for i, num := range nums {
numAndIndicesnum = append(numAndIndicesnum, i) }
for i, num := range nums {
wantSecondVal := target - num
if !ok {
continue
}
for _, index := range indices {
if i == index {
continue
}
return []int{i,index}
}
}
return []int{}
}
アプローチ1
2重ループで愚直に答えを探す
時間計算量: O(n^2)
空間計算量: O(1)
アプローチ2
アプローチ1から2重ループを消すためにmapを使う
時間計算量: O(n)
空間計算量: O(n)
となる。一般的にメモリのほうが増やしやすいのでこうするとパフォーマンスが良くなる
x + y = targetなので、y = target -x であることを利用する。