---
# System prepended metadata

title: Leetcode 1. Two Sum
tags: [Array]

---

###### 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.
    <br>
    <br>
    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.
    <br>
    <br>
Only one valid answer exists.
    <br>
    <br>
    
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>
    <br>
<li>思考流程</li>
    <ul>
        <li>暴力解</li>
        利用第一個 for loop 來固定住 array element, A，再利用第二個 for loop 遍歷整個 array，找尋有沒有 array element, B 與 A 相加後可以等於 target 值。如果有就回傳 A 和 B 的索引值。
        <br>
        <br>
        這裡要注意的是，要避免自己相加自己為 target 的情況。
        <br>
        <br>
        Time Complexity: O(n^2); Space Complexity: O(1)
        <br>
        <br>
        <li>Hashmap</li>
        需要額外準備一個 hashmap( 以 Python 為例就是 dictionary 結構 )來儲存資訊。遍歷整個 array( 從索引值為 0 開始 )，儲存每一個當前的 array element 為 key，其索引值為 value。在遍歷的時候，同時檢查 hashmap 內是否存在 target - array[i] 的 key。若存在即找到相加為 target 的兩個元素，回傳其索引值；若不存在則繼續遍歷剩下的 array elements。
        <br>
        <br>
        Time Complexity: O(n); Space Complexity: O(n)
        <br>
        <br>
        <li>排序法</li>
        首先對 array elements 進行排序。對於排序好的 array，利用左右兩個指標從 array 的頭尾開始遍歷，如果相加小於 target 就讓左指標往右移動，相加大於 target 就讓右指標往左移動。當發現兩個 array elements 相加等於 target 時，即回傳他們的索引值。
        <br>
        <br>
        Time Complexity: O(nlogn); Space Complexity: O(1) ~ O(n)
        <br>
        <br>
    </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>