LeetCode — Two Sum II — Input Array Is Sorted

題目連結：167. Two Sum II — Input Array Is Sorted
難度：easy

題目大意：
尋找 sorted array 中哪兩個位置的數加總為 target。

解題過程：
【version 1】
1. 以一個 int boundary 去找尋大略的搜尋範圍
2. 用迴圈從 0 ~ boundary 找尋配對的數字
3. 以 unordered_map 記錄經過的 number，並以 find() 搜尋
【version 2】
1. 因為是已排序的 vector，所以設定兩個 index，分別從最前面及最後面y sum
2. 若 sum < target，left++（往較大數字移動）；反之，則 right- -

使用語言：C++

實作程式如下：

version 1

時間複雜度：O(N²)，N 為 numbers.size()，考慮 find() 最差時間為 O(N)
空間複雜度：O(N)

Runtime: 4 ms, faster than 87.37% of C++ online submissions for Two Sum II — Input Array Is Sorted.
Memory Usage: 9.6 MB, less than 44.66% of C++ online submissions for Two Sum II — Input Array Is Sorted.

version 2

時間複雜度：O(N)
空間複雜度：O(1)

Runtime: 0 ms, faster than 100.00% of C++ online submissions for Two Sum II — Input Array Is Sorted.
Memory Usage: 9.4 MB, less than 99.93% of C++ online submissions for Two Sum II — Input Array Is Sorted.