Masalah Dua Jumlah' pada LeetCode

Huraian Masalah
Memandangkan tatasusunan nombor integer dan sasaran integer, kembalikan indeks dua nombor yang ditambah kepada sasaran.

Tandatangan Fungsi Go:
func twoSum(bilangan []int, int sasaran) []int
Contoh 1:
Input: angka = [2,7,11,15], sasaran = 9
Output: [0,1]
Penjelasan: Kerana nums[0] nums[1] == 9, kami kembalikan [0, 1].
Contoh 2:

Input: angka = [3,2,4], sasaran = 6
Output: [1,2]
Contoh 3:

nput: angka = [3,3], sasaran = 6
Output: [0,1]
Penyelesaian 1: Pendekatan Brute Force

Penyelesaian 1: Pendekatan Brute-Force (Gelung Bersarang)
Dalam pendekatan ini, anda menyemak setiap pasangan elemen untuk melihat sama ada ia menjumlahkan kepada sasaran. Ini melibatkan lelaran melalui tatasusunan dengan dua gelung bersarang.

Kod

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
}

Analisis Kerumitan

Penyelesaian 2: Jadual Hash Dua Laluan
Penyelesaian ini menambah baik pendekatan brute-force dengan menggunakan peta cincang untuk menyimpan nilai dan indeks setiap elemen dalam laluan pertama. Dalam pas kedua, anda menyemak sama ada pelengkap (iaitu, sasaran - num) wujud dalam peta cincang.

Kod

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
}

Penyelesaian 3: Jadual Hash Satu Laluan (Penyelesaian Optimum)

• Pendekatan ini menggabungkan kedua-dua sisipan dan carian dalam satu laluan. Semasa anda mengulangi tatasusunan, anda:

• Semak sama ada pelengkap (iaitu, sasaran - num) wujud dalam peta cincang.

• Jika pelengkap ditemui, kembalikan indeks.

• Jika tidak, tambahkan elemen semasa dan indeksnya pada peta cincang untuk carian masa hadapan.
  Kod
  

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
}

Analisis Kerumitan

• Kerumitan Masa: ?(?)

  • Hanya satu laluan melalui tatasusunan diperlukan, menjadikannya ini mendekati linear dalam kerumitan masa.

• Kerumitan Angkasa:o(n)

  • Peta cincang menyimpan setiap elemen dan indeksnya.

Kebaikan dan Keburukan
Kebaikan: Pendekatan paling cekap untuk kerumitan masa, dengan pelaksanaan yang bersih dan padat.
Keburukan: Tiada, kerana ia mencapai kerumitan masa dan ruang yang optimum untuk masalah ini.

Atas ialah kandungan terperinci Masalah Dua Jumlah' pada LeetCode. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!