*#1.Two Sum*

### Problem statement

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**

```
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Explanation: Because nums[0] + nums[1] == 9, we return [0, 1].
```

**Example 2**

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

**Example 3**

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

### Explanation

從給定的 `array`

中找到兩個數相加等於 `target`

，並且返回兩數索引

- 只會有一個有效答案
- 同一個元素不會使用兩次
- 可以返回任何順序的索引

### Solution

比較直覺地方式是使用雙迴圈迭代陣列來解，這種暴力解法遇到資料量較大時，需要更多時間來完成。

如果以時間複雜度作為考量，需設法減少迴圈的使用次數，讓執行時間大幅下降，那麼可使用一個額外空間來儲存元素，以達到空間換時間的想法，雖然此方法讓時間複雜度降低，同時也提高了空間複雜度。

**Array**

透過雙迴圈逐一走訪陣列，因為元素不可重複，故取 i+1 略過自己以及計算過的值

```
public int[] TwoSum(int[] nums, int target)
{
int i, j;
for (i = 0; i < nums.Length; i++)
for (j = i + 1; j < nums.Length; j++)
if (nums[i] + nums[j] == target)
return new int[] { i, j };
return null;
}
```

**HashTable**

使用一個額外空間 `HashTable`

，以達到用空間換取時間

```
public int[] TwoSum(int[] nums, int target)
{
Hashtable hash = new Hashtable();
for (int i = 0; i < nums.Length; i++)
{
int num = nums[i];
int diff = target - num;
if (hash.ContainsKey(diff))
return new int[] { i, (int)hash[diff] };
if (!hash.ContainsKey(num))
hash.Add(num, i);
}
return null;
}
```

**Dictionary**

一樣使用一個額外空間 `Dictionary`

達到空間換時間的目的

```
public int[] TwoSum(int[] nums, int target)
{
Dictionary<int, int> dic = new Dictionary<int, int>();
for (int i = 0; i < nums.Length; i++)
{
int num = nums[i];
int diff = target - num;
if (dic.ContainsKey(diff))
return new int[] { i, (int)dic[diff] };
if (!dic.ContainsKey(num))
dic.Add(num, i);
}
return null;
}
```

### Reference

Thanks for reading the article 🌷 🌻 🌼

If you like it, please don't hesitate to click heart button ❤️

or click like on my Leetcode solution

or follow my GitHub ⭐

or buy me a coffee ⬇️ I'd appreciate it.

## Top comments (0)