JJ's Blog

1. 題目（Problem Statement）

英文：

Given an array of integers nums and an integer target, return the indices of the two numbers such that they add up to target.

You may assume that each input would have exactly one solution, and you may not use the same element twice.

You can return the answer in any order.
中文：

給定一個整數陣列 nums 和一個整數 target，返回兩個數字的索引，這兩個數字的和等於 target。

你可以假設每個輸入都只有一個解，而且你不可以使用相同的元素兩次。

你可以以任何順序返回答案。

2. 題目說明與解決方案（Explanation and Solution）

這個問題要求給定一個整數陣列 nums 和一個整數 target，找出陣列中兩個數字的索引，使得這兩個數字的和等於 target。你可以假設每個輸入只有一個解，並且不可以使用相同的元素兩次。最後，你需要返回這兩個數字的索引。

這個問題的解決方案是使用哈希表（Dictionary 或 Python 的字典）來記錄每個數字和其對應的索引。我們遍歷整個陣列一次，對於每個元素，計算出目標值減去該元素的差值，我們稱之為 complement。然後，檢查這個 complement 是否已經存在於哈希表中。

如果存在，則找到了答案，我們可以返回這兩個數字的索引，一個是 complement 的索引，另一個是目前元素的索引。這樣我們就能保證這兩個數的和等於目標值 target。

如果遍歷完整個陣列都找不到答案，則拋出異常（C# 使用 ArgumentException，Python 使用 ValueError），表示找不到解。

這個解法的時間複雜度是 O(N)，其中 N 為陣列的長度，因為我們只需遍歷一次陣列。空間複雜度也是 O(N)，用於存儲哈希表，其中 N 是陣列中不同數字的數量。這個方法能夠高效地找到兩個數字的索引，使其和等於目標值。

3. 範例（Example）

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

4. 限制條件（Constraints）

整數陣列 nums 的長度介於 2 到 10^4 之間。
每個元素的值介於 -10^9 到 10^9 之間。
目標值 target 的值介於 -10^9 到 10^9 之間。

5. C# 解法（C# Solution）

 1namespace UnitTestDay1_TwoSum
 2{
 3    public class Solution
 4    {
 5        public int[] TwoSum( int[] nums, int target )
 6        {
 7            Dictionary<int, int> numIndexMap = new Dictionary<int, int>();
 8
 9            for (int i = 0; i < nums.Length; i++)
10            {
11                int complement = target - nums[i];
12                if (numIndexMap.ContainsKey( complement ))
13                {
14                    return new int[] { numIndexMap[complement], i };
15                }
16                numIndexMap[nums[i]] = i;
17            }
18
19            throw new ArgumentException( "No solution found." );
20        }
21    }
22}

6. C# 程式碼說明（C# Code Explanation）

我們首先建立一個 Dictionary（哈希表） numIndexMap，用來儲存數字和其對應的索引。
接著使用一個 for 迴圈遍歷整個陣列 nums。
在每個迭代中，我們計算目標值 target 減去目前元素 nums[i] 的差值，稱為 complement。
檢查 complement 是否已經存在於 numIndexMap 中，如果存在，表示找到了答案。
如果找到答案，則返回一個包含 complement 在哈希表中的索引以及目前元素的索引的整數陣列。
如果遍歷完整個陣列都找不到答案，則拋出 ArgumentException，表示找不到解。
這個解法具有時間複雜度為 O(N)，其中 N 為陣列的長度，因為我們僅遍歷一次陣列。空間複雜度也是 O(N)，用於存儲哈希表，其中 N 是陣列中不同數字的數量。

這個 C# 解法使用哈希表（Dictionary）來記錄每個數字對應的索引。我們遍歷一次整個陣列，對於每個元素，計算目標值減去該元素的差值 complement。然後檢查這個 complement 是否已經存在於哈希表中，如果存在，就找到了答案，返回這兩個數字的索引。如果遍歷完整個陣列都找不到答案，則拋出異常。

7. C# 單元測試（C# Unit Tests）

 1namespace UnitTestDay1_TwoSumTests
 2{
 3    [TestClass()]
 4    public class SolutionTests
 5    {
 6        private Solution UT = new Solution();
 7
 8        [TestMethod()]
 9        public void Test1()
10        {
11            int[] nums = { 2, 7, 11, 15 };
12            int target = 9;
13            int[] expected = { 0, 1 };
14            int[] actual = UT.TwoSum( nums, target );
15            CollectionAssert.AreEqual( expected, actual );
16        }
17
18        [TestMethod()]
19        public void Test2()
20        {
21            int[] nums = { 3, 2, 4 };
22            int target = 6;
23            int[] expected = { 1, 2 };
24            int[] actual = UT.TwoSum( nums, target );
25            CollectionAssert.AreEqual( expected, actual );
26        }
27
28        [TestMethod()]
29        public void Test3()
30        {
31            int[] nums = { 3, 3 };
32            int target = 6;
33            int[] expected = { 0, 1 };
34            int[] actual = UT.TwoSum( nums, target );
35            CollectionAssert.AreEqual( expected, actual );
36        }
37    }
38}

8. Python 解法（Python Solution）

1class Solution:
2    def twoSum(self, nums, target):
3        num_index_map = {}
4        for i, num in enumerate(nums):
5            complement = target - num
6            if complement in num_index_map:
7                return [num_index_map[complement], i]
8            num_index_map[num] = i
9        raise ValueError("No solution found.")

9. Python 程式碼說明（Python Code Explanation）

我們使用一個 Python 字典（Dictionary） num_index_map 來記錄數字和其對應的索引。
使用 enumerate 函數來獲取每個數字的索引和值。
在每個迭代中，計算目標值 target 減去目前元素 nums[i] 的差值，稱為 complement。
檢查 complement 是否已經存在於 num_index_map 中，如果存在，表示找到了答案。
如果找到答案，則返回一個包含 complement 在字典中的索引以及目前元素的索引的整數陣列。
如果遍歷完整個陣列都找不到答案，則拋出 ValueError，表示找不到解。
這個解法具有時間複雜度為 O(N)，其中 N 為陣列的長度，因為我們僅遍歷一次陣列。空間複雜度也是 O(N)，用於存儲字典，其中 N 是陣列中不同數字的數量。

這個 Python 解法使用哈希表（Dictionary）來記錄每個數字對應的索引。我們遍歷一次整個陣列，對於每個元素，計算目標值減去該元素的差值 complement。然後檢查這個 complement 是否已經存在於哈希表中，如果存在，就找到了答案，返回這兩個數字的索引。如果遍歷完整個陣列都找不到答案，則拋出異常。

10. Python 單元測試（Python Unit Tests）

 1import unittest
 2
 3class TestTwoSum(unittest.TestCase):
 4
 5  def test_case_1(self):
 6	  nums = [2, 7, 11, 15]
 7    target = 9
 8    expected = [0, 1]
 9    actual = Solution().twoSum(nums, target)
10    self.assertEqual(expected, actual)
11
12  def test_case_2(self):
13    nums = [3, 2, 4] 
14    target = 6
15    expected = [1, 2]
16    actual = Solution().twoSum(nums, target)
17    self.assertEqual(expected, actual)
18
19  def test_case_3(self):
20    nums = [3, 3]
21    target = 6
22    expected = [0, 1]
23    actual = Solution().twoSum(nums, target) 
24    self.assertEqual(expected, actual)
25
26if __name__ == '__main__':
27  unittest.main()

11. 總結（Summary）

這個題目要求找到一對數字，它們的和等於目標值 target。使用雙重迴圈會過慢，改用雜湊表儲存數字和索引可以降低時間複雜度到 O(N)，所以我們使用哈希表（dictionary）來加速查找，降低時間複雜度。

時間複雜度：O(n)，其中 n 是陣列 nums 的長度。
空間複雜度：O(n)，我們使用一個哈希表（dictionary）來儲存數字與它們的索引，最壞情況下需要儲存所有數字。

解題技巧在於善用雜湊表快速查找是否存在補數，避免使用兩層迴圈。時間複雜度從 O(N^2) 降到 O(N)，空間複雜度為 O(N)。

這是一道很典型的使用雜湊表優化時間複雜度的題目，適合用來練習基礎算法技巧。

補充說明

哈希表（Hash Table）是一種非常高效的資料結構，可以在 O(1) 的時間複雜度內完成插入、查詢和刪除操作。

哈希表的基本原理是:

使用哈希函数（Hash Function）將鍵(Key)映射到表中一個位置。這個位置就叫做該鍵的哈希值（Hash Value）。
根据哈希值將資料儲存在表的對應位置。不同的鍵可能會經哈希函数映射到同一個位置,這種情況就叫做衝突（Collision）。衝突的解決方法有開放定址法和鏈地址法。
查詢時根據鍵再次計算哈希值,從表中對應位置獲取資料。

哈希表的優點是：

查詢速度極快,平均可在 O(1) 時間內完成。
可以快速插入和刪除資料。
存儲空間較陣列更加靈活。
可以快速判斷某個鍵是否存在。
支持不同資料類型的鍵。

哈希表的缺點是：

無法獲取所有資料,只能通過鍵值查找。
需要額外處理哈希碰撞。
存儲空間較陣列稍大。

LeetCode #1 Two Sum