DAY 0
0
Software Development

# 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]
Output: 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 <= 105`
• `109 <= nums[i] <= 109`
• `109 <= target <= 109`
• Only one valid answer exists.

### 1. 最暴力解

• Time: O(n^2)
• Space: O(1)
``````var twoSum = function(nums, target) {
for (let i = 0; i < nums.length - 1; i++) {
for (let j = i+1; j < nums.length; j++) {
if (nums[i]+nums[j] === target) {
let result = [i, j]
return result
}
}
}
};
``````

### 2. Hash Table

1. 降低 time complexity
2. 我們想要確認element是否存在
3. 我們想知道 element 的 index 位置
4. 如果沒有 collision, hash table 的 lookup 是 linear time
• Time: O(n)
• Space: O(n)
``````var twoSum = function(nums, target) {
let map = {}
// 第一個 loop:
// 把 value & index 加進去 hash table
for (let i = 0; i < nums.length; i++) {
map[nums[i]] = i
}
// 第二個 loop:
// 檢查他們的complemet(= target-value)是否在table中,
// 且不能為他自己, 用 index 來檢查
for (let i = 0; i < nums.length; i++) {
let complement = target - nums[i]
// 若有找到且不為自己，回傳
if (map[complement] != null && map[complement] != i) {
return [i, map[complement]]
}
}
}
``````

• Time: O(n)
• Space: O(n)