LeetCode の「2 つの和の問題」-Golang-php.cn

LeetCode の「2 つの和の問題」

Barbara Streisand

リリース： 2024-11-16 15:30:03

オリジナル

161 人が閲覧しました

Two Sum Problem’ on LeetCode

問題の説明
整数 nums の配列と整数ターゲットを指定すると、ターゲットに加算される 2 つの数値のインデックスを返します。

Go 関数の署名:
func twoSum(nums []int, target int) []int
例 1:
入力: 数値 = [2,7,11,15]、ターゲット = 9
出力: [0,1]
説明: nums[0] nums[1] == 9 であるため、[0, 1] を返します。
例 2:

入力: 数値 = [3,2,4]、ターゲット = 6
出力: [1,2]
例 3:

入力: 数値 = [3,3]、ターゲット = 6
出力: [0,1]
解決策 1: ブルートフォースアプローチ

解決策 1: ブルートフォースアプローチ (ネストされたループ)
このアプローチでは、要素の各ペアをチェックして、合計が目標に達するかどうかを確認します。これには、2 つのネストされたループを使用して配列を反復処理することが含まれます。

コード

func twoSum(nums []int, target int) []int {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] + nums[j] == target {
                return []int{i, j}
            }
        }
    }
    return nil
}

ログイン後にコピー

複雑さの分析

解決策 2: 2 パスハッシュテーブル
このソリューションは、最初のパスでハッシュマップを使用して各要素の値とインデックスを保存することにより、ブルートフォースアプローチを改善します。 2 番目のパスでは、補数 (つまり、ターゲット - 数値) がハッシュマップに存在するかどうかを確認します。

コード

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    // First pass: populate the map with each element's index
    for i, num := range nums {
        numMap[num] = i
    }
    // Second pass: check for the complement
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok && i != j {
            return []int{i, j}
        }
    }
    return nil
}

ログイン後にコピー

解決策 3: ワンパスハッシュテーブル (最適な解決策)

このアプローチでは、挿入と検索の両方を 1 つのパスで組み合わせます。配列を反復処理すると、次のようになります:
補数 (つまり、ターゲット - 数値) がハッシュマップに存在するかどうかを確認します。
補数が見つかった場合は、インデックスを返します。
そうでない場合は、今後の検索のために現在の要素とそのインデックスをハッシュマップに追加します。
コード

func twoSum(nums []int, target int) []int {
    numMap := make(map[int]int)
    for i, num := range nums {
        if j, ok := numMap[target - num]; ok {
            return []int{j, i}
        }
        numMap[num] = i
    }
    return nil
}

ログイン後にコピー

複雑さの分析