程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> LeetCode實踐之一 Two Sum

LeetCode實踐之一 Two Sum

編輯:關於C++

題目描述:
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
可能出現的badcase: 答案中存在一個數為target/2時。
實現思路:若第一層遍歷數1,第二層遍歷數2,則時間復雜度O(n2)遍歷。若僅進行第一遍遍歷,在尋找第二個數的時候使用Hash表存儲數據,則時間復雜度為O(n),此時需要注意badcase問題。

實現代碼如下:

  1. class Solution {
  2. public:
  3. vector twoSum(vector &numbers, int target) {
  4. map hash_map;
  5. vector r;
  6. for (int i=0; i != numbers.size(); ++i)
  7. {
  8. hash_map[numbers[i]] = i;
  9. }
  10. for(int i=0; i != numbers.size(); ++i)
  11. {
  12. map::iterator it = hash_map.find(target-numbers[i]);
  13. if (it != hash_map.end())
  14. {
  15. if(i+1 == it->second+1)
  16. continue;
  17. r.push_back(min(i+1, it->second+1));
  18. r.push_back(max(i+1, it->second+1));
  19. }
  20. }
  21. return r;
  22. }
  23. };
  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved