[Leetcode]第1題Two sum的解法與思路

最近在學習軟體中
覺得刷 leetcode 好像是必經的過程
只好踏入這令人頭痛的荊棘之路…
沒想到每一題都讓我不知道從何起手
所以我決定每寫完一題都要進行記錄並且學習其他最優解！

題目介紹：1.Two Sum

#

LeetCode 的第一題 Two Sum 是經典的基礎演算法題
考察數組遍歷、哈希表（Hash Table）的應用
以及時間複雜度優化的能力。

題目描述

#

給定一個整數數組 nums 和一個目標值 target，請在該數組中找出和為目標值的兩個數，並返回它們的索引。

你可以假設每個輸入都只會有一組有效解，但同一個元素不能被重複使用。

範例 1：

nums = [2, 7, 11, 15]
target = 9

輸出：

[0, 1]

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

應用概念

#

在解這道題之前，我們需要了解幾個核心概念：

1. 數組遍歷（Array Iteration）
   • 我們需要遍歷數組來尋找兩個數字，使它們的總和等於 target。
2. 哈希表（Hash Table）
   • 使用字典（dict）可以快速查找數字是否已經存在，提高查找效率。
3. 時間複雜度
   • 暴力解法（O(n²)） 需要雙重迴圈，效率較低。
   • 哈希表解法（O(n)） 透過字典來記錄數值和索引，一次遍歷即可完成查找。

初步解析

#

問了 chatgpt 後
才知道有很多不同種的解法
以下為範例的兩種

解法 1：暴力解法（Brute Force，O(n²)）

#

思路

#

這是我思考了半小時後才想到的笨方法…
使用雙重迴圈，針對 nums 中的每個數 nums[i]
去檢查 nums[j] 是否能與之相加得到 target。
並在最後輸出[i,j]

其中的range(len(nums))指讓 i 運行這個串列的長度的次數的意思

程式碼

#

def two_sum(nums, target):
    for i in range(len(nums)):  # 第一層遍歷
        for j in range(i + 1, len(nums)):  # 第二層遍歷
            if nums[i] + nums[j] == target:
                return [i, j]
    return []

時間複雜度

#

• 內外兩層迴圈，每層最多需要 n 次運算，所以總共 O(n²)。
• 缺點：對於大數據集合，效率較低。

解法 2：哈希表解法（Hash Table，O(n)）

#

思路

#

為了加快查找速度，我們可以使用 dict 來儲存數字與其索引值。
這樣在遍歷數組時，可以在 O(1) 的時間內查找是否已經有對應的數值。

程式碼

#

def two_sum(nums, target):
    num_dict = {}  # 建立一個哈希表來儲存數值與索引
    for i, num in enumerate(nums):
        complement = target - num  # 需要的數值
        if complement in num_dict:  # 查詢哈希表
            return [num_dict[complement], i]
        num_dict[num] = i  # 加入哈希表
    return []

解釋

#

建立一個字典 num_dict 來存放數值和索引。
遍歷 nums，對於每個 num，計算它對應的補數 complement = target - num。
如果 complement 在 num_dict 中，代表我們已經找到答案，直接回傳索引。
否則，把當前數字 num 和它的索引 i 存入 num_dict。

時間複雜度

#

• O(n)：只需要一次遍歷，查找 dict 是 O(1)。

最終總結

#

最佳解法

#

• 哈希表解法是最推薦的方法，因為它的時間複雜度是 O(n)。

以上是我目前解題的思路
其實自己對於解法 2 的哈希表也還在理解中
未來還會繼續嘗試寫 leetcode 的題目
但應該都是先從簡單開始練手…
有問題歡迎留言討論！