# LeetCode Solution, Easy, 1. Two Sum # [1. Two Sum](https://leetcode.com/problems/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:** ```text Input: nums = [2,7,11,15], target = 9 Output: [0,1] Explanation: Because nums[0] + nums[1] == 9, we return [0, 1]. ``` **Example 2:** ```text Input: nums = [3,2,4], target = 6 Output: [1,2] ``` **Example 3:** ```text 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? ### 題目翻譯 ## 解法解析 官方提供了三種解法：暴力破解、兩次遍歷 Hash Table、一次遍歷 Hash Table 其中最後的兩種方式，空間複雜度和時間複雜度相同。 這邊採用的是 One-pass Hash Table 的解法，因為覺得只使用一次遍歷的解法比較簡潔 這邊以 JavaScript 做範例 1. 先建立一個 Hash Table 2. 使用迴圈將參數 `nums` 做遍歷 3. 在每一次的遍歷中，將 `nums` 中的元素和 `target` 做相減得到 `diff` 4. 如果在 Hash Table 中不存在則存入其中，如果已經存在則回傳 而在 Memory 更優化的方式，是不另外使用 Hash Table 來做儲存，直接將 `diff` 在 `nums` 做查找。因為有些程式語言沒有支援類似 `indexOf()` 的語法糖，所以會用第二層回圈做判斷 第一步，先使用 `for` 迴圈去遍歷傳入的 `nums` 陣列。 第二步，將 `target` 減去每次 `nums` 遍歷的值 `diff`， `diff` 就是我們希望在陣列 `nums` 中找到的另一個配對的值。 第三步，將 `diff`放到 `map` 中判斷，是否已經存在，如果不存在就暫存此次遍歷的值和其 index 到 `map` 中。如果找到了就將找到的兩個 index 放在陣列回傳 ### 解法範例 #### Go ##### Runtime ```go 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 ```go 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 ```javascript /** * @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 ```javascript /** * @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 ```kotlin class Solution { fun twoSum(nums: IntArray, target: Int): IntArray { val hash = mutableMapOf() 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 ```kotlin 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 ```php 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 ```php 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 ```python 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 ```python 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 ```rust use std::collections::HashMap; impl Solution { pub fn two_sum(nums: Vec, target: i32) -> Vec { 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 ```rust impl Solution { pub fn two_sum(nums: Vec, target: i32) -> Vec { 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 ```swift 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 ```swift class Solution { func twoSum(_ nums: [Int], _ target: Int) -> [Int] { for i in 0..