LeetCode 上的“二和問題”

問題描述
給定一個整數數組 nums 和一個整數目標，傳回兩個數字相加達到目標的索引。

Go 函數簽章：
func TwoSum(nums []int, target int) []int
範例1：
輸入：nums = [2,7,11,15]，目標 = 9
輸出：[0,1]
解釋：因為 nums[0] nums[1] == 9，所以我們回傳 [0, 1].
範例2：

輸入：nums = [3,2,4]，target = 6
輸出：[1,2]
範例 3：

輸入：nums = [3,3]，目標= 6
輸出：[0,1]
解決方案1：暴力法

解 1：暴力破解方法（嵌套循環）
在這種方法中，您檢查每對元素以查看它們的總和是否達到目標。這涉及到使用兩個嵌套循環迭代數組。

代碼

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：二次雜湊表
該解決方案透過使用哈希映射在第一遍中儲存每個元素的值和索引來改進暴力方法。在第二遍中，您檢查哈希映射中是否存在補集（即 target - num）。

代碼

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：一次性雜湊表（最佳解）

• 這種方法在一次傳遞中結合了插入和尋找。當您迭代數組時，您：

• 檢查雜湊映射中是否存在補集（即 target - num）。

• 如果找到補集，則回傳索引。

• 如果沒有，則將當前元素及其索引新增至雜湊映射中以供將來查找。
  代碼
  

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
}

複雜性分析

• 時間複雜度: ?(?)

  • 只需要一次遍歷數組，使得 時間複雜度接近線性。

• 空間複雜度:o(n)

  • 雜湊映射儲存每個元素及其索引。

優點和缺點
優點：時間複雜度最有效的方法，具有乾淨、緊湊的實作。
缺點：無，因為它實現了這個問題的最佳時間和空間複雜度。

以上是LeetCode 上的“二和問題”的詳細內容。更多資訊請關注PHP中文網其他相關文章！