題目在問什麼

給一個整數陣列 nums 和目標值 target，要找出兩個數字的索引，讓它們相加剛好等於 target。

題目保證：

  • 每組輸入都恰好有一組答案
  • 同一個元素不能重複使用

例子

Input: nums = [2, 7, 11, 15], target = 9
Output: [0, 1]

第一個直覺解法

最直接的做法就是雙層迴圈，枚舉每一組 (i, j)，檢查 nums[i] + nums[j] 是否等於 target。

這樣寫很直觀，但時間複雜度是 O(n^2)，陣列變長時效率會明顯下降。

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        int res1 = 0;
        int res2 = 0;

        for (int i = 0; i < nums.Length; i++)
        {
            for (int j = i + 1; j < nums.Length; j++)
            {
                if (nums[j] == target - nums[i])
                {
                    res1 = i;
                    res2 = j;
                }
            }
        }

        return new int[2] { res1, res2 };
    }
}

更好的解法

這題真正關鍵是把問題換個角度看。

當我走到 nums[i] 時，我其實不是在問「它能不能跟誰配對」，而是在問：

target - nums[i] 這個數，我之前有沒有看過？

只要用一個 Dictionary<int, int> 記錄「數值 -> 索引」，每次先查補數，再決定是否把當前值放進字典，就能在一次遍歷內完成。

解題思路

流程如下：

  1. 準備一個字典，記錄遍歷過的數值與索引
  2. 走訪每個元素時計算 remain = target - nums[i]
  3. 如果字典裡已經有 remain，代表答案找到了
  4. 如果還沒有，就把目前值和索引存進字典，給後面元素使用

這樣每個元素最多只進出一次，整體就能壓到 O(n)。

public class Solution
{
    public int[] TwoSum(int[] nums, int target)
    {
        int[] res = new int[2] { -1, -1 };
        Dictionary<int, int> targetDict = new Dictionary<int, int>();

        for (int i = 0; i < nums.Length; i++)
        {
            int remain = target - nums[i];

            if (targetDict.TryGetValue(remain, out res[0]))
            {
                res[1] = i;
                break;
            }

            if (!targetDict.ContainsKey(nums[i]))
            {
                targetDict.Add(nums[i], i);
            }
        }

        return res;
    }
}

複雜度

  • 時間複雜度：O(n)
  • 空間複雜度：O(n)

這題先記住的重點

  • 雙層迴圈能解，但不是最好的解法
  • 這題的核心是把「找兩數相加」轉成「查補數是否已出現」
  • Dictionary 是這題最自然的優化方向