【leetcode】 算法題1 兩數之和 問題 ?　 給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。

你可以假設每個輸入只對應一種答案，且同樣的元素不能被重復利用。

示例:

?

給定 nums = [2, 7, 11, 15], target = 9因為 nums[0] + nums[1] = 2 + 7 = 9 所以返回 [0, 1] 代碼實現 #include <vector> #include <map> /** * *給定一個整數數組和一個目標值，找出數組中和為目標值的兩個數。 *你可以假設每個輸入只對應一種答案，且同樣的元素不能被重復利用。 *case: *給定 nums = [2, 7, 11, 15], target = 9 *因為 nums[0] + nums[1] = 2 + 7 = 9 *所以返回 [0, 1] */ using namespace std; class Solution { public:// 兩兩對比的方式，時間復雜度為O(n2)vector<int> twoSum(vector<int>& nums, int target) {vector<int> ret;// 第一種/*for (int i = 0; i < nums.size(); i++) {for (int j = i + 1; j < nums.size(); j++) {if (nums[i] + nums[j] == target) {ret.push_back(i);ret.push_back(j);return ret;}}}*/// 第二種：數據插入到hashmap里，然后通過target - nums[i]來確定，時間復雜度為O(2n)map<int, int> m;for (int i = 0; i < nums.size(); i++) {m[nums[i]] = i;}for (int i = 0; i < nums.size(); i++) {if (m.count(target - nums[i]) > 0 && i != m[target - nums[i]]) {ret.push_back(i);ret.push_back(m[target - nums[i]]);return ret;}}return ret;} };

　　

?

推薦 posted on 2018-05-10 14:29 川山甲 閱讀(...) 評論(...) 編輯 收藏

轉載于:https://www.cnblogs.com/baochuan/p/9019465.html

總結

以上是生活随笔為你收集整理的【leetcode】 算法题1 两数之和的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。