跳到主要內容
Jasonmel Online

演算法

同一個問題，不同的解題思路

主題 · 考題：Two Sum

考題：Two Sum

在陣列裡找兩個加起來等於目標的數：暴力兩層迴圈、排序後雙指標、雜湊表一次掃過，成本從 n² 一路降到 n。

解法
目標
10
題目
給一個陣列 nums 和目標 target，回傳兩個不同位置的索引，使它們的值加起來等於 target。例如 nums = [2, 7, 11, 15]、target = 9 → [0, 1]。
1/17
nums · target = 66
  1. 72
    0
  2. 4
    1
  3. 46
    2
  4. 8
    3
  5. 76
    4
  6. 48
    5
  7. 49
    6
  8. 17
    7
  9. 27
    8
  10. 55
    9
雜湊表：數值 → 索引
    正在檢查已記進雜湊表答案

    找兩個位置，數值加起來等於 66。

    同一份輸入，所有解法
    解法答案檢查＋排序比較額外記憶體Big O
    暴力兩層迴圈[6, 7] (49 + 17)400O(n²)
    排序＋雙指標[6, 7] (49 + 17)2910 格O(n log n)
    雜湊表一次掃過[6, 7] (49 + 17)87 格O(n)
    亮起來的是這一步執行的程式碼
    function twoSumBrute(nums: number[], target: number): [number, number] | null {
      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 null;
    }
     
    function twoSumSorted(nums: number[], target: number): [number, number] | null {
      // Sort indices, not values: the answer is the original positions.
      const order = nums.map((_, i) => i).sort((a, b) => nums[a] - nums[b]);
      let lo = 0, hi = order.length - 1;
      while (lo < hi) {
        const sum = nums[order[lo]] + nums[order[hi]];
        if (sum === target) {
          return [Math.min(order[lo], order[hi]), Math.max(order[lo], order[hi])];
        }
        if (sum < target) lo++;
        else hi--;
      }
      return null;
    }
     
    function twoSumHash(nums: number[], target: number): [number, number] | null {
      const seen = new Map<number, number>();                  // value -> first index
      for (let i = 0; i < nums.length; i++) {
        const j = seen.get(target - nums[i]);
        if (j !== undefined) return [j, i];
        if (!seen.has(nums[i])) seen.set(nums[i], i);
      }
      return null;
    }

    模型假設與範圍

    • Big O 與實測步數以頁面列出的基本操作為單位；視覺化的快照、畫圖、程式高亮和輸出成本另計，不是執行時間 benchmark。

    什麼時候用

    • 面試官要看的是你能不能從暴力解一路優化：先講兩層迴圈（O(n²)、正確但慢），再指出瓶頸是「找另一半」這一步，最後用雜湊表把它變成一次查詢。
    • 記憶體很緊、或輸入本來就排好序時，排序＋雙指標是很好的替代：O(1) 額外空間（已排序時）而且不用雜湊。

    和其他主題的關係

    時間與空間複雜度（Big O）

    操作平均最差
    暴力兩層迴圈
    額外空間 O(1)
    		O(n²)O(n²)
    排序＋雙指標
    排序佔大頭；索引陣列 O(n) 空間
    		O(n log n)O(n log n)
    雜湊表一次掃過
    最差是雜湊全部碰撞；O(n) 空間
    		O(n)O(n²)

    空間：O(1) / O(n) / O(n)，依序是暴力、排序、雜湊

    Big O 實測：n 變大時步數怎麼長

    數的是：檢查次數（排序法含排序比較），無解的輸入

    Big On = 250n = 500n = 1,000n = 2,000成長倍數：實測（理論）
    暴力兩層迴圈O(n²)31,125124,750499,5001,999,000×64 (×64)
    排序＋雙指標O(n log n)1,4683,5378,12218,168×12 (×11)
    雜湊表一次掃過O(n)2505001,0002,000×8.0 (×8.0)

    和其他做法比

    n = 250n = 500n = 1,000n = 2,000
    暴力兩層迴圈31,125124,750499,5001,999,000
    排序＋雙指標1,4683,5378,12218,168
    雜湊表一次掃過2505001,0002,000

    沒有解的輸入（最差情況）：每種做法都得做完全部的工作。n 從 250 變成 2,000，暴力法的檢查次數變成 64 倍，雜湊表只變成 8 倍。排序法的數字包含排序本身的比較次數。

    真實世界裡的它

    • 變形：輸入已排序（LeetCode 167）→ 直接雙指標；3Sum → 排序後固定一個數，剩下做雙指標，O(n²)。
    • 追問：要回傳所有解？有重複數字？資料流一筆筆進來（設計一個 add / find 的類別）？

    取捨與陷阱

    • 排序之後索引就變了：要排的是索引，或把（值, 原索引）一起排。
    • 同一個元素不能用兩次：雜湊表要先查再存，否則 target = 2×x 時會配到自己。
    • 雜湊表平均 O(1)，最差 O(n)：面試時說「平均」比較精確。

    LeetCode 練習