面試白板題：陣列與字串

為什麼要練白板題？

💡 比喻：考駕照的路考 你可能很會開車，但路考時還是要練固定的考試路線。 白板題也一樣——它不代表你的全部能力， 但它是面試這場遊戲的規則，練過就不怕。

題目一：Two Sum（兩數之和）

題目說明

給定一個整數陣列和一個目標值，找出陣列中兩個數字相加等於目標值的索引。

暴力解法 O(n²)

// 暴力解法：雙重迴圈檢查所有配對 // Brute force: check all pairs
public int[] TwoSumBruteForce(int[] nums, int target) // 兩數之和暴力解
{
    for (int i = 0; i < nums.Length; i++) // 外層迴圈走訪每個元素
    {
        for (int j = i + 1; j < nums.Length; j++) // 內層迴圈檢查後面的元素
        {
            if (nums[i] + nums[j] == target) // 如果兩數相加等於目標值
            {
                return new int[] { i, j }; // 回傳兩個索引
            }
        }
    }
    return Array.Empty<int>(); // 找不到就回傳空陣列
}

優化解法 O(n) — 使用 Dictionary

// 優化解法：用 Dictionary 記錄已看過的數字 // Optimized: use Dictionary
public int[] TwoSumOptimized(int[] nums, int target) // 兩數之和優化解
{
    var map = new Dictionary<int, int>(); // 建立字典存放「值 → 索引」
    for (int i = 0; i < nums.Length; i++) // 走訪陣列一次
    {
        int complement = target - nums[i]; // 計算需要的互補數字
        if (map.ContainsKey(complement)) // 如果字典中有互補數字
        {
            return new int[] { map[complement], i }; // 回傳兩個索引
        }
        map[nums[i]] = i; // 把當前數字和索引存入字典
    }
    return Array.Empty<int>(); // 找不到就回傳空陣列
}

時間複雜度分析

暴力解：O(n²) — 兩層迴圈，每個元素都要跟其他元素比較
優化解：O(n)  — 只走訪一次陣列，Dictionary 查詢是 O(1)
空間複雜度：O(n) — Dictionary 最多存 n 個元素

題目二：Reverse String（反轉字串）

暴力解法 — 新建字串

// 暴力解法：從後面往前建立新字串 // Brute force: build new string backwards
public string ReverseStringSimple(string s) // 反轉字串簡單版
{
    char[] result = new char[s.Length]; // 建立同長度的字元陣列
    for (int i = 0; i < s.Length; i++) // 走訪每個字元
    {
        result[i] = s[s.Length - 1 - i]; // 從後面取字元放到前面
    }
    return new string(result); // 轉換回字串並回傳
}

優化解法 — 雙指標原地反轉

// 優化解法：雙指標從兩端往中間交換 // Optimized: two pointers swap in-place
public void ReverseStringInPlace(char[] s) // 原地反轉字元陣列
{
    int left = 0; // 左指標從開頭開始
    int right = s.Length - 1; // 右指標從結尾開始
    while (left < right) // 當左指標還沒超過右指標
    {
        char temp = s[left]; // 暫存左邊的字元
        s[left] = s[right]; // 把右邊的字元放到左邊
        s[right] = temp; // 把暫存的字元放到右邊
        left++; // 左指標往右移
        right--; // 右指標往左移
    }
}

時間複雜度分析

兩種解法時間都是 O(n)
但原地反轉的空間複雜度是 O(1)，不需要額外空間！

題目三：Valid Parentheses（有效括號）

題目說明

給定一個只包含 '('、')'、'{'、'}'、'['、']' 的字串，判斷括號是否有效配對。

使用 Stack 解法

// Stack 解法：遇到左括號推入，遇到右括號彈出比對 // Stack solution
public bool IsValidParentheses(string s) // 檢查括號是否有效
{
    var stack = new Stack<char>(); // 建立字元堆疊
    var pairs = new Dictionary<char, char> // 定義括號配對關係
    {
        { ')', '(' }, // 右括號對應左括號
        { '}', '{' }, // 右大括號對應左大括號
        { ']', '[' }  // 右中括號對應左中括號
    };

    foreach (char c in s) // 走訪字串中的每個字元
    {
        if (pairs.ContainsKey(c)) // 如果是右括號
        {
            if (stack.Count == 0 || stack.Pop() != pairs[c]) // 堆疊空或不配對
            {
                return false; // 回傳無效
            }
        }
        else // 如果是左括號
        {
            stack.Push(c); // 推入堆疊
        }
    }
    return stack.Count == 0; // 堆疊清空代表全部配對成功
}

時間複雜度分析

時間複雜度：O(n) — 走訪字串一次
空間複雜度：O(n) — 最差情況堆疊存放所有字元

題目四：Palindrome Check（迴文檢查）

暴力解法 — 反轉比較

// 暴力解法：反轉字串後比較 // Brute force: reverse and compare
public bool IsPalindromeBrute(string s) // 迴文檢查暴力版
{
    string cleaned = new string( // 清理字串：只保留英數字並轉小寫
        s.Where(char.IsLetterOrDigit) // 篩選字母和數字
         .Select(char.ToLower) // 全部轉小寫
         .ToArray()); // 轉成字元陣列
    string reversed = new string(cleaned.Reverse().ToArray()); // 反轉字串
    return cleaned == reversed; // 比較是否相同
}

優化解法 — 雙指標

// 優化解法：雙指標從兩端往中間比較 // Optimized: two pointers
public bool IsPalindromeOptimized(string s) // 迴文檢查優化版
{
    int left = 0; // 左指標
    int right = s.Length - 1; // 右指標
    while (left < right) // 當兩指標還沒交會
    {
        while (left < right && !char.IsLetterOrDigit(s[left])) // 跳過非英數字元
            left++; // 左指標右移
        while (left < right && !char.IsLetterOrDigit(s[right])) // 跳過非英數字元
            right--; // 右指標左移
        if (char.ToLower(s[left]) != char.ToLower(s[right])) // 比較兩端字元
            return false; // 不同就不是迴文
        left++; // 左指標右移
        right--; // 右指標左移
    }
    return true; // 全部比完都相同，是迴文
}

時間複雜度分析

暴力解：O(n) 時間，O(n) 空間（建立新字串）
優化解：O(n) 時間，O(1) 空間（不需要額外空間）

🤔 我這樣寫為什麼會錯？

錯誤一：Two Sum 忘記檢查同一個元素

// ❌ 錯誤：同一個元素用了兩次 // Wrong: using same element twice
var map = new Dictionary<int, int>(); // 建立字典
for (int i = 0; i < nums.Length; i++) // 先把所有數字加入字典
    map[nums[i]] = i; // 存入字典
for (int i = 0; i < nums.Length; i++) // 再走訪一次
{
    int complement = target - nums[i]; // 計算互補值
    if (map.ContainsKey(complement)) // 有找到
        return new[] { i, map[complement] }; // ❌ 可能 i == map[complement]
}

// ✅ 正確：邊走邊查，確保不會用到同一個元素 // Correct: check while iterating
var map2 = new Dictionary<int, int>(); // 建立字典
for (int i = 0; i < nums.Length; i++) // 走訪一次
{
    int complement = target - nums[i]; // 計算互補值
    if (map2.ContainsKey(complement)) // 如果之前已經存過互補值
        return new[] { map2[complement], i }; // 一定是不同元素
    map2[nums[i]] = i; // 存入當前元素
}

錯誤二：括號檢查忘記處理空堆疊

// ❌ 錯誤：沒檢查堆疊是否為空就 Pop // Wrong: Pop without checking
if (stack.Pop() != pairs[c]) // ❌ 堆疊可能是空的，會拋出例外

// ✅ 正確：先檢查堆疊再 Pop // Correct: check before Pop
if (stack.Count == 0 || stack.Pop() != pairs[c]) // 先確認堆疊不為空

面試小提示

1. 先釐清題目：問清楚邊界條件（空陣列？重複元素？）
2. 先說暴力解：讓面試官知道你會做，再優化
3. 分析複雜度：每個解法都要能說出時間和空間複雜度
4. 寫程式碼前先說思路：不要埋頭就寫
5. 測試：寫完後用範例 input 走一遍程式碼