LeetCode實現兩數求和

本篇內容介紹了“LeetCode實現兩數求和”的有關知識，在實際案例的操作過程中，不少人都會遇到這樣的困境，接下來就讓小編帶領大家學習一下如何處理這些情況吧！希望大家仔細閱讀，能夠學有所成！

題目描述

給定一個整數數組nums和一個目標值target，請你在該數組中找出和為目標值的那兩個整數，并返回他們的數組下標。
你可以假設每種輸入只會對應一個答案。但是，你不能重復利用這個數組中同樣的元素。

示例:

<pre><code> 給定 nums = [2, 7, 11, 15], target = 9 因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] </code></pre>

解法一 暴力解法

解題思路

最容易想到的就是暴力法，使用兩個遍歷，查找兩數之和是否為target。流程如下：

1. 使用i來遍歷數組每個元素

2. 在i的每一個循環中，使用j從i + 1開始遍歷

3. 判斷i和j對應的值的和是否為target

代碼實現

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 []int{}
}

復雜度分析

• 時間復雜度: O(n^2)。一共有兩次循環，每次循環的事件復雜度是O(n)。總的復雜度為O(n^2)。

• 空間復雜度: O(1)。

解法二 哈希表解法

解題思路

該解法中會借助一個哈希表。在遍歷數組時，會將當前元素添加到哈希表中。并且會檢查哈希表中是否已經存在當前元素所對應的目標元素。如果存在就返回。

代碼實現

func twoSum2(nums []int, target int) []int {
    m := make(map[int]int)
    for i := 0; i < len(nums); i ++ {
        if index, exists := m[target - nums[i]]; exists {
            return []int{i,index}
        }
        m[nums[i]] = i
    }
    return []int{}
}

復雜度分析

• 時間復雜度：O(n)。我們只遍歷了一次數組。

• 空間復雜度：O(n)。使用了哈希表，需要額外的空間。取決于哈希表中存儲的元素數量，該表最多需要存儲O(n)個元素。

“LeetCode實現兩數求和”的內容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業相關的知識可以關注億速云網站，小編將為大家輸出更多高質量的實用文章！