# 1. Two Sum

## 題目敘述

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]
``````

Constraints:

• `2 <= nums.length <= 10**4`
• `-10**9 <= nums[i] <= 10**9`
• `-10**9 <= target <= 10**9`
• Only one valid answer exists.

Follow-up: Can you come up with an algorithm that is less than `O(n**2)` time complexity?

Hint 1:

A really brute force way would be to search for all possible pairs of numbers but that would be too slow. Again, it's best to try out brute force solutions for just for completeness. It is from these brute force solutions that you can come up with optimizations.

Hint 2:

So, if we fix one of the numbers, say `x`, we have to scan the entire array to find the next number `y` which is `value - x` where value is the input parameter. Can we change our array somehow so that this search becomes faster?

Hint 3:

The second train of thought is, without changing the array, can we use additional space somehow? Like maybe a hash map to speed up the search?

## 解法解析

1. 先建立一個 Hash Table
2. 使用迴圈將參數 `nums` 做遍歷
3. 在每一次的遍歷中，將 `nums` 中的元素和 `target` 做相減得到 `diff`
4. 如果在 Hash Table 中不存在則存入其中，如果已經存在則回傳

### 解法範例

#### Go

##### Runtime
``````func twoSum(nums []int, target int) []int {
hash := make(map[int]int)

for i, num := range nums {
if j, ok := hash[target-num]; ok {
return []int{j, i}
}
hash[num] = i
}

return []int{}
}
``````
##### Memory
``````func twoSum(nums []int, target int) []int {
n := len(nums)
for i := 0; i < n-1; i++ {
for j := i + 1; j < n; j++ {
if nums[i]+nums[j] == target {
return []int{i, j}
}
}
}
return []int{}
}
``````

#### JavaScript

##### Runtime
``````/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
const map = new Map();

for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i];
if (map.has(diff)) return [i, map.get(diff)];
map.set(nums[i], i);
}
};
``````
##### Memory
``````/**
* @param {number[]} nums
* @param {number} target
* @return {number[]}
*/
var twoSum = function (nums, target) {
for (let i = 0; i < nums.length; i++) {
const diff = target - nums[i];

if (nums.includes(diff) && i !== nums.indexOf(diff)) {
return [nums.indexOf(diff), i];
}
}
};
``````

#### Kotlin

##### Runtime
``````class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
val hash = mutableMapOf<Int, Int>()

for ((index, num) in nums.withIndex()) {
var diff = target - num
if (hash.containsKey(diff)) {
return intArrayOf(hash.getValue(diff), index)
}

hash[num] = index
}

return intArrayOf()
}
}
``````
##### Memory
``````class Solution {
fun twoSum(nums: IntArray, target: Int): IntArray {
for ((index, num) in nums.withIndex()) {
var diff = target - num

if (nums.contains(diff) && nums.indexOf(diff) != index) {
return intArrayOf(nums.indexOf(diff), index)
}
}

return intArrayOf()

}
}
``````

#### PHP

##### Runtime
``````class Solution
{

/**
* @param Integer[] \$nums
* @param Integer \$target
* @return Integer[]
*/
function twoSum(\$nums, \$target)
{
\$map = [];
\$size = count(\$nums);
for (\$i = 0; \$i < \$size; \$i++) {
\$complement = \$target - \$nums[\$i];
if (array_key_exists(\$complement, \$map)) {
return [\$i, \$map[\$complement]];
}
\$map[\$nums[\$i]] = \$i;
}
}
}
``````
##### Memory
``````class Solution
{

/**
* @param Integer[] \$nums
* @param Integer \$target
* @return Integer[]
*/
function twoSum(\$nums, \$target)
{
for (\$i = 0; \$i < sizeof(\$nums); \$i++) {
for (\$j = \$i + 1; \$j < sizeof(\$nums); \$j++) {
if (\$nums[\$i] + \$nums[\$j] === \$target) {
return [\$i, \$j];
}
}
}
}
}
``````

#### Python

##### Runtime
``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
hashmap = {}
for i in range(len(nums)):
complement = target - nums[i]
if complement in hashmap:
return [i, hashmap[complement]]
hashmap[nums[i]] = i
``````
##### Memory
``````class Solution:
def twoSum(self, nums: List[int], target: int) -> List[int]:
for i in range(len(nums)):
diff = target - nums[i]

if diff in nums and i is not nums.index(diff):
return [i, nums.index(diff)]
``````

#### Rust

##### Runtime
``````use std::collections::HashMap;

impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
let mut hash_map = HashMap::with_capacity(nums.len());

for (idx, &num) in nums.iter().enumerate() {
let complement = target - num;
if let Some(&find_target) = hash_map.get(&complement) {
return vec![find_target as i32, idx as i32];
}
hash_map.insert(num, idx);
}

vec![]
}
}
``````
##### Memory
``````impl Solution {
pub fn two_sum(nums: Vec<i32>, target: i32) -> Vec<i32> {
if nums.len() == 2 {
return vec![0, 1];
}

for (i, x) in nums.iter().enumerate() {
for (j, y) in nums.iter().enumerate().filter(|(j, _)| *j != i) {
if x + y == target {
return vec![i as i32, j as i32];
}
}
}

vec![]
}
}
``````

#### Swift

##### Runtime
``````class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
var hash: [Int : Int] = [:]

for (i, num) in nums.enumerated() {
if let index = hash[target - num] {
return [index, i]
}

hash[num] = i
}

return []
}
}
``````
##### Memory
``````class Solution {
func twoSum(_ nums: [Int], _ target: Int) -> [Int] {
for i in 0..<nums.count {
for j in (i + 1)..<nums.count {
var sum = nums[i] + nums[j]

if (sum == target) {
return [i, j]
}
}
}

return []
}
}
``````