Leetcode 1. Two Sum

###### tags: `Array` <h1>Leetcode 1. Two Sum</h1> <ol> <li>問題描述</li> 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. Only one valid answer exists. 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] <li>Input的限制</li> <ul> <li>2 <= nums.length <= 10^4</li> <li>-10^9 <= nums[i] <= 10^9</li> <li>-10^9 <= target <= 10^9</li> </ul> <li>思考流程</li> <ul> <li>暴力解</li> 利用第一個 for loop 來固定住 array element, A，再利用第二個 for loop 遍歷整個 array，找尋有沒有 array element, B 與 A 相加後可以等於 target 值。如果有就回傳 A 和 B 的索引值。 這裡要注意的是，要避免自己相加自己為 target 的情況。 Time Complexity: O(n^2); Space Complexity: O(1) <li>Hashmap</li> 需要額外準備一個 hashmap( 以 Python 為例就是 dictionary 結構 )來儲存資訊。遍歷整個 array( 從索引值為 0 開始 )，儲存每一個當前的 array element 為 key，其索引值為 value。在遍歷的時候，同時檢查 hashmap 內是否存在 target - array[i] 的 key。若存在即找到相加為 target 的兩個元素，回傳其索引值；若不存在則繼續遍歷剩下的 array elements。 Time Complexity: O(n); Space Complexity: O(n) <li>排序法</li> 首先對 array elements 進行排序。對於排序好的 array，利用左右兩個指標從 array 的頭尾開始遍歷，如果相加小於 target 就讓左指標往右移動，相加大於 target 就讓右指標往左移動。當發現兩個 array elements 相加等於 target 時，即回傳他們的索引值。 Time Complexity: O(nlogn); Space Complexity: O(1) ~ O(n) </ul> <li>測試</li> <ul> <li>test 1</li> Input: nums = [1, 5, 4, 3, 9], target = 13 Output: [2, 4] <li>test 2( worst case case for hashmap )</li> Input: nums = [1, 3, 5, 6], target = 11 Output: [2, 3] <li>array elements less than two( edge case )</li> 如果不計 array 的大小，空陣列或是只有一個元素的陣列，就會造成演算法無法處理的情況，需要例外處理。 <li>some array elements are not numbers( edge case )</li> 如果沒有規範 input 一定要是數字，出現字串類的的 input 則需要另外處理。 </ul> </ol>