title: Leetcode-02 - 两数之和
date: 2022-02-12 22:23:14
toc: true
index_img: https://b3logfile.com/file/2022/02/image-51e4a586.png
category:
- leetcode
tags: - leetcode
暴力枚举#
配列内の各数値 x を列挙し、配列内に target-x が存在するかどうかを探します。
func twoSum(nums []int, target int) []int {
for i := 0; i < len(nums); i++ {
for j := i + 1; j < len(nums); j++ {
if nums[j] == target-nums[i] {
return []int{i, j}
}
}
}
return nil
}
最悪の場合、配列内の任意の 2 つの数値は一度ずつマッチする必要があります。
ハッシュテーブル#
暴力的な列挙方法では、target - x を探すための時間計算量が高すぎるため、この問題を解決するためにハッシュテーブルを作成できます。
func twoSum(nums []int, target int) []int {
result := make(map[int]int, 0)
for index, value := range nums {
if val, ok := result[target-value]; ok {
return []int{index, val}
}
result[value] = index
}
return nil
}
参考資料#
- オリジナルの問題：1. 两数之和 - 力扣（LeetCode）