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]解答
其實最簡單的想法，兩個 for 迴圈就可以解決了，但時間複雜度非常的高 O(n²)。
- Runtime: 6696 ms, faster than 5.46%
- Memory Usage: 13.9 MB, less than 60.44%
第二種方法就是使用 hash table ，因為題目有說您可以假定每個輸入都只有一個解決方案，並且您可能不會兩次使用同一元素，所以不會有 collision 的問題。
Hash Table 的核心概念，主要有兩個，第一個就是快速索引通常只需要 O(1)的時間就可以索引到，第二個就是降低記憶體空間浪費，但是 hash table 使用時還是要非常注意，例如下列的範例就是 collision 就會很刺激了，所以通常 hash table 放的時候會有兩種策略 linear probing 及 quadratic probing。
- h(26)=26 mod 6=2
- h(50)=50 mod 6=2
- Runtime: 36 ms, faster than 88.29%.
- Memory Usage: 14 MB, less than 39.79%.
One more thing
本題的目標主要是想呈現，演算法不同導致明顯的速度差別，所以 faster 超過多少 % 倒是不是非常重要了…. ，那在 memory 方面因為我們需要多一個 table 儲存自然的 memory 使用上就會較多。
