圖解LeetCode(入門篇): 1. Two Sum

16th鐵人賽

zaleyu

2024-08-10 12:34:30

517 瀏覽

分享至

前言

許多人在面對 LeetCode 問題時可能會感到無從下手。在這次為期三十天的鐵人賽中，我計劃每天從 Easy 題庫中選取一題，並以圖解的方式進行解析。希望透過這種方式，能夠幫助初學者更好地理解 LeetCode 的解題思路，進而激發讀者的興趣，自主練習解題。

1. Two Sum

題目描述：

給定一個整數陣列 nums 和一個整數目標值 target，請在該陣列中找到兩個數字，使它們的和等於目標值，並返回這兩個數字的索引。

你可以假設每個輸入都只有一個解答。此外，陣列中的同一元素不能在答案中重複使用。

你可以按任意順序返回答案。
Example 1:

Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].

解題思路：
我們在第一次解 LeetCode 時，可以從最直觀的暴力法入手。以第一題 Two Sum 為例，最簡單的解法是使用兩層 for 迴圈。第一層迴圈遍歷題目給定的 nums 陣列，第二層迴圈則從第一層迴圈選取的數字之後開始，再次遍歷 nums 陣列。這樣，我們可以檢查每一對數字是否滿足兩數之和等於目標值 target。

var twoSum = function(nums, target) {
    for (let i = 0; i < nums.length; i++) {
        for (let j = i + 1; j < nums.length; j++) {
            if (nums[i] + nums[j] === target) {
                return [i, j];
            }
        }
    }
    return [];
};

這樣的解法的時間複雜度為 O(n²)，其中 n 是陣列的長度。對於每個元素，內層迴圈會遍歷剩下的所有元素，這使得整體複雜度呈現平方級別。通常來說，在 LeetCode 解題中，如果使用兩層以上的 for 迴圈來解題，這樣的解法通常不會是最優解。因為當陣列的長度變得很長時，這樣的解法會過於耗時，無法有效處理大數據量的情況。

時間複雜度:
描述演算法隨著輸入數據量增長，執行時間的變化。它衡量了演算法的效率，幫助我們比較不同演算法的優劣。常見的時間複雜度包括 O(1)、O(log n)、O(n) 和 O(n²)。
O(1):是最理想的時間複雜度，因為無論數據量多大，執行時間都不變。
O(n²):執行時間隨著輸入數據量的平方增長。這意味著當數據量增加一倍，執行時間會增加到原來的四倍。

回到使用兩層 for 迴圈的解法中，我們透過這兩層迴圈來記錄兩個數字相加時的索引。不過，俗話說得好，空間可以換取時間。也就是說，我們可以優化解法，僅使用一層迴圈來達到同樣的效果。具體來說，我們在遍歷陣列時，將每個數字的索引存儲在記憶體中，並計算 target 減去當前數字的差值。如果這個差值在之前的遍歷中已經存儲在記憶體中，則說明我們找到了兩個數字，它們的和等於目標值。這樣，我們不僅減少了時間複雜度，還提升了算法的效率。

function twoSum(nums, target) {
    const map = new Map();

    for (let i = 0; i < nums.length; i++) {
        const complement = target - nums[i];

        if (map.has(complement)) {
            return [map.get(complement), i];
        }

        map.set(nums[i], i);
    }

    return [];
}

在這裡，我使用 JavaScript 的 Map 來撰寫程式。讀者可以根據自己的習慣選擇使用不同的編程語言來解 LeetCode，並不限於 JavaScript。例如，你可以使用 Python 的 dictionary 或 C++ 的 unordered_map。由於工作需要，我對 JavaScript 相當熟悉，因此接下來的解題示範都將使用 JavaScript。

回到這個優化解法，因為我們利用空間來換取時間，所以空間複雜度從原本的 O(1) 增加到 O(n)，但時間複雜度從 O(n²) 改進到 O(n)。由於現代計算機的記憶體通常足夠應付這些額外的開銷，因此在軟體工程中，我們通常會選擇使用時間複雜度較優的解法來提高性能和效率。

空間複雜度:
描述演算法在執行過程中所需的內存空間如何隨著輸入數據量的增長而變化。簡單來說，它衡量了一個演算法在運行時需要多少額外的內存。常見的空間複雜度有：
O(1): 演算法所需的額外空間是固定的，與數據量無關。
O(n): 所需的內存空間隨著輸入數據量線性增長。
O(n²): 內存需求隨數據量的平方增長。

總結：
至此，我們成功解決了 LeetCode 的第一題。儘管這是一道難度標記為 Easy 的題目，但透過解題的思考過程與圖解，相信能夠為讀者帶來不少啟發。最後，筆者習慣將每道 LeetCode 題目的解法進行分類，這樣在日後整理和歸納時會更加方便。對於這道題，我們可以將其歸類為「For 迴圈」和「Memory」這兩個分類。當鐵人賽進行到最後一天時，我們可以回顧這些分類，從中看出 LeetCode 為我們帶來了哪些觀念和解題思路。這樣的回顧不僅能夠幫助我們鞏固學到的知識，也能讓這些解題策略更加深刻地印在腦海中，為未來的挑戰做好準備。相信透過這樣的整理和總結，大家對於解題技巧會有更深的理解與掌握。