題目:
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
思路:
最直接的思路當然是兩兩嘗試,但是這樣的時間復雜度為O(n2),這樣的時間復雜度不到萬不得已還是不要接受,再嘗試思考,如果能用target減去數組中的一個數然後得到結果再到數組中搜尋,如果能找到即可,這樣的話無疑就需要一個能搜索的數據結構了,想到map,先遍歷一遍簡歷搜索庫,然後再按照以上思路進行,這樣的時間復雜度為O(n),代價是以空間換時間,這樣是不是最優解呢?以後再慢慢思考吧,反正我的這段代碼是通過了leetcode OJ的。
代碼:
class Solution { public: vectortwoSum(vector &numbers, int target) { std::map finder; for (int i = 0; i (val, i)); } for (int i = 0; i re; if(finder[left]==i) { continue; } else if (finder[left]