雖然題目簡單，但我這好不容易優化到前2%，感覺也值得分享給大家（方法比較偷機）
題目：
給定一個整數陣列 nums 和一個目標值 target，請你在該陣列中找出和為目標值的那 兩個 整數，并回傳他們的陣列下標，
你可以假設每種輸入只會對應一個答案，但是，你不能重復利用這個陣列中同樣的元素，
示例:
來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/two-sum
著作權歸領扣網路所有，商業轉載請聯系官方授權，非商業轉載請注明出處，
給定 nums = [2, 7, 11, 15], target = 9
因為 nums[0] + nums[1] = 2 + 7 = 9
所以回傳 [0, 1]
我的解答：
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int>& nums, int target) { 4 vector<int> res(2); 5 int endPos = nums.size(); 6 //vector記憶體是連續的 這里直接取地址 7 //這樣后面訪問時不需要呼叫vecotr的成員函式 8 //因為不清楚編譯器優化級別 9 int *numArr = &nums[0];10 11 if (endPos < 5)12 {13 //陣列長度比較小時使用原始的雙回圈法更快點14 for (int i = 0; i < endPos; ++i)15 {16 //遍歷陣列，找出每個元素與target之差做為尋找目標17 int nNeed = target - numArr[i];18 for (int j = i + 1; j < endPos; ++j)19 {20 //在后面找，看有沒有與目標相同的數字21 if (numArr[j] == nNeed)22 {23 //如果有直接回傳24 res[0] = i;25 res[1] = j;26 return res;27 }28 }29 }30 }31 32 //陣列比較大時使用一次遍歷哈希查找的方法比較快33 map<int, int> mpNums;34 pair<map<int, int>::iterator, bool> pairRet;35 //int numCurr;36 37 //遍歷陣列38 for (int i = 0; i < endPos; ++i)39 {40 //把當前數值當key，當前位置當value插入map41 //numCurr = numArr[i]; //實驗發現這里使用numCurr取值代替numArr[i]反而慢了42 //看來讀取消耗遠低于寫43 pairRet = mpNums.insert(make_pair(numArr[i], i));44 45 //如果插入成功（大部分情況下是插入成功的）46 if (pairRet.second)47 {48 //查看map里面是否有目前值-當前元素值的資料存在49 //如果有就說明找到目標50 int numNeed = target - numArr[i];51 map<int, int>::iterator it = mpNums.find(numNeed);52 if (it != mpNums.end() && it->second != i)53 {54 //題目要求不能重復使用自己，所以需要限制it->second != i55 res[0] = it->second;56 res[1] = i;57 return res;58 }59 }60 else61 {62 //如果插入失敗說明63 //已經在map存在相同數值，則看它們加起來是否等于target64 if ((numArr[i] << 1) == target) //2 * numArr[i]65 {66 res[0] = pairRet.first->second;67 res[1] = i;68 return res;69 }70 }71 }72 73 res.clear();74 return res;75 }76 77 };
執行結果：通過顯示詳情執行用時 :8 ms, 在所有 cpp 提交中擊敗了98.11%的用戶記憶體消耗 :10.1 MB, 在所有 cpp 提交中擊敗了37.46%的用戶
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/86640.html
標籤：C++