> ## Content Index
> Fetch the complete content index at: https://blog.anthea.day/llms.txt
> Use this file to discover other available public pages before exploring further.

# LeetCode 1. Two Sum
- URL: https://blog.anthea.day/leetcode-c-e5-88-b7-e9-a1-8c-e7-ad-86-e8-a8-98-1/
- Published: 2022-12-17T10:15:40.000Z
- Updated: 2026-11-07T18:26:09.000Z
- Author: Anthea / 芫荽
- Tags: #Migrated-1792241843742, #Import 2026-10-17 12:57, Coding, LeetCode 刷題筆記

> Given an array of integers `nums` and an integer `target`, return 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.

**Example 1:**

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

**Example 2:**

```makefile
Input: nums = [3,2,4], target = 6 
Output: [1,2]
```

**Example 3:**

```makefile
Input: nums = [3,3], target = 6 
Output: [0,1]
```

---

### 直覺

兩個 `for` 迴圈，加起來相等就回傳（不能自己加自己）。

```csharp
for (var i = 0; i < nums.Length; i++) 
{ 
    for (var j = 0; j < nums.Length; j++) 
    { 
        if (i == j) continue; 
 
        var sum = nums[i] + nums[j]; 
        if (sum == target) return new[] { i, j }; 
    } 
} 
 
return new int[] { };
```

結果：Runtime 210ms / Memory 44.1MB

---

### 調整迴圈數量

兩個迴圈的做法是用兩個變數相加，一個迴圈就只會有一個變數 `nums[i] `可以利用，也就是說會變成：

```csharp
sum = nums[i] + unknown
```

而我們的目標是要找出兩個數字相加等於 `target`，現在有第一個可能的數字 `nums[i]` 了，第二個數字就是 `unknown`。從上面可以看出來：

```csharp
unknown = sum - nums[i]
```

而 sum == target 是我們的條件，所以可以改寫成：

```csharp
unknown = target - nums[i]
```

這樣就解掉一個迴圈了。於是我們只要去比對 `unkown` 是否存在於 `nums` 中，是的話就找出他的 `index` 即可。程式碼就會變成：

```csharp
for (var i = 0; i < nums.Length; i++) 
{ 
    var remain = target - nums[i]; 
    var indexOfRemain = Array.IndexOf(nums, remain); 
     
    if (indexOfRemain >= 0 && indexOfRemain != i) 
    { 
        return new []{i, indexOfRemain}; 
    } 
} 
 
return new int[] { };
```

結果：Runtime 190ms / Memory 44.1MB

---

### 改變被搜尋物件

`Dictionary` 在執行搜尋的時候會比較快，改成用 `Dictionary` 接搜尋過的數字 `Key `和他的索引 `Value`，如果還沒找過這個數字就加到 `Dictionary` 內，如果有找過，也就是這個 `Key` 存在於 `Dictionary` 內，就把他的 `Value`，也就是索引抓出來回傳：

```csharp
var usedNums = new Dictionary<int, int>(); 
for (var i = 0; i < nums.Length; i++) 
{ 
    var remain = target - nums[i]; 
    if (usedNums.ContainsKey(remain)) 
    { 
        return new[] { usedNums[remain], i }; 
    } 
    else 
    { 
        usedNums[nums[i]] = i; 
    } 
} 
 
throw new ArgumentException();
```

結果：Runtime 149ms / Memory 44.8MB

---

### 參考資料

- [1\. Two Sum](https://leetcode.com/problems/two-sum/description/?ref=blog.anthea.day)
- [浅析C# Dictionary实现原理](https://www.cnblogs.com/incerry/p/10325290.html?ref=blog.anthea.day)