【Leetcode 筆記】 1. Two sum

題目解釋

在這題中，我們給定一個整數陣列 nums 和一個整數 target，要求我們返回兩個數字的 index，使它們的和等於 target。 假設每個輸入只會有一個解，並且我們不能使用相同的元素兩次。

範例

• 輸入: nums = [2, 7, 11, 15], target = 9
• 輸出: [0, 1]

因為 nums[0] + nums[1] = 2 + 7 = 9，所以我們返回 [0, 1]。

最佳解法

建立一個 hash map，若 hash map 裡面沒有該數值的 key，就將 {'數值': index} 的 pair 加入 hash map。

如此一來，我們就可以根據數值來快速尋找他在 array 中的 index。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        hash_map = dict()

        for i in range(0, len(nums)):
            find = target - nums[i]

            if find in hash_map:
                return [i, hash_map[find]]
            else:
                hash_map[nums[i]] = i

時間複雜度

O(n)，其中 n 是 nums 的長度。因為我們只 traverse 了一次 array，每次 search 和 insert 新資料進去 hash map 的操作都是 O(1)。

空間複雜度

O(n)，其中 n 是 nums 的長度。這是因為在最壞情況下，hash map 中需要儲存所有 array 中的 element 。

暴力解法

下面是使用暴力解法的 code，這個方法要 traverse 兩次才能找到答案，時間複雜度是 O(n^2)。

class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        for i in range(len(nums) - 1):
            for j in range(i + 1, len(nums)):
                if nums[i] + nums[j] == target:
                    return [i, j]

• About
• Latest Posts

數據女巫 𝔻.𝕡𝕪𝕤 🔮

𝐀𝐈 𝐀𝐫𝐭𝐢𝐬𝐭 • 𝐒𝐨𝐟𝐭𝐰𝐚𝐫𝐞 𝐄𝐧𝐠𝐢𝐧𝐞𝐞𝐫
﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊﹊
致力於打破現有框架的 AI 藝術創作者，曾接受藝文雜誌的個人專訪，作品於香港實體展出。有擔任大學講座講師與 Stable Diffusion AI 年會講者的經驗。擅長 Live Prompting，曾獲 GIGABYTE VS AI 街頭對戰冠軍、ASUS 校園 AI 繪圖競賽亞軍等殊榮。
---
歡迎合作邀約 / 委託 / 各式交流
ᴇᴍᴀɪʟ：dpys@techmagichouse.art

Latest posts by 數據女巫 𝔻.𝕡𝕪𝕤 🔮 (see all)

• [推薦工具] 讓程式碼截圖變的美美的吧！VScode CodeSnap 與 3 種同功能線上工具介紹 - 2025-01-05
• [AI 繪圖初級教學] 用 X/Y/Z Plot 比較 Stable Diffusion 的 prompt 與 LoRA 效果 - 2024-12-27
• [AI 繪圖中級篇教學] Stable Diffusion WebUI WD14 Tagger 介紹 - 2024-12-26