怎麼樣，學習完前3章之後有沒有按捺不住？是不是已經不滿足於做課後練習了呢？
恰好今天是周末，時間比較寬裕，我們來刷一道leetcode
連結https://leetcode.com/problems/two-sum/
題目給定一個整型數組和另外一個整數，在數組找出兩個整數，使得它們的和等於給定的整數。返回這兩個整數的下標。
假設總能找到這樣的兩個數，且結果唯一
給定 nums = [ 2, 7, 11, 15 ], target = 9,
因為 nums[ 0 ] + nums[ 1 ] = 2 + 7 = 9,
return [ 0, 1 ].
弄懂了題目的意思之後我們就正式開始解題了。
這裡建議大家先自己嘗試一下。
第一回合可能最容易想到的一個方法就是通過兩個循環來解決這個問題
外層循環從0開始遍歷：[ 02, 07, 11 ]
內層循環從1開始遍歷：[ 07, 11, 15 ]
如果對應位置上的整數相加等於給定的值，則返回下標
我們把頁面往下拖動，在下拉框裡面選擇」c++」，就可以開始擼代碼了。
建議大家先去寫寫看，多想幾種解題方法出來。
想到之後在網站上就可以直接編碼了，不需要藉助IDE。
我是這麼寫的：
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> vecResult; for( int i = 0; i < nums.size() - 1; ++i ) { for( int j = i + 1; j < nums.size(); ++j ) { if( nums[i] + nums[j] == target ) { vecResult.push_back( i ); vecResult.push_back( j ); return vecResult; } } } return vecResult; } };
點擊 「Run Code」，哦也，一次通過！
點擊 「Submit Solution」，OK, Accepted!
點擊 「Detail」 看一看，天啊擼，什麼鬼。耗時809ms！擊敗了5.6%的用戶！
這他媽的跟360提示開機速度擊敗了全國1%的用戶一樣埋汰人啊！！！
仔細研究研究：
nums.size()調用了太多次，如果先調用一次把結果存起來呢？
OK，
點擊 「Edit Code」，修改代碼
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> vecResult; auto iSize = nums.size(); for( int i = 0; i < iSize - 1; ++i ) { for( int j = i + 1; j < iSize; ++j ) { if( nums[i] + nums[j] == target ) { vecResult.push_back( i ); vecResult.push_back( j ); return vecResult; } } } return vecResult; } };
提交之後再來看一下詳情，我擦，486ms了！擊敗了33.49%的用戶！！！
提升了20多個百分點啊，查看一下被接受的提交總數是273183，這乘下來一下子前進了五萬多名。自信心激增，有木有！！！
再一看，iSize - 1也調用了好多次，同樣的問題嘛。好，也把它給提前存下來試試看。
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> vecResult; auto iSize = nums.size(); auto iOutterSize = iSize - 1; for( int i = 0; i < iOutterSize; ++i ) { for( int j = i + 1; j < iSize; ++j ) { if( nums[i] + nums[j] == target ) { vecResult.push_back( i ); vecResult.push_back( j ); return vecResult; } } } return vecResult; } };
提交，shit，496ms！怎麼還耗時增加了？ 難道定義一個臨時量這麼影響性能結果？
到底是怎麼回事，各路大神能告訴我嗎？
想了半天沒想能，先把問題記錄下來。咱們繼續。
書上說可以用列表初始化的方式來初始化數組，咱們把返回值的地方改一改，看看能不能有所提升
ok
第三回合class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { auto iSize = nums.size(); for( int i = 0; i < iSize - 1; ++i ) { for( int j = i + 1; j < iSize; ++j ) { if( nums[i] + nums[j] == target ) { return { i, j }; } } } vector<int> vecResult; return vecResult; } };
499ms？這個統計沒問題吧？
不過書上也說了，建議創建空的vector，然後動態添加元素。看來動態添加的效率果然要高一些
我們把 return { i, j } 改成創建一個臨時量再返回試試
vector<int> temp = { i, j }; return temp;
652ms，果然創建一個臨時量挺佔用時間的
當然這些都是我們粗淺的解釋，在沒有接觸到更多知識之前不妨把這些記下來，留著以後探索。
想想還有什麼可以改的？？？
序列中的元素有三種訪問方式
我們只用了下標，範圍for不容易用到這來，不如我們先試試迭代器？
第四回合class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { vector<int> vecResult; int i = 0; for( auto itr = nums.begin(); itr != nums.end() - 1; ++itr) { int j = i + 1; for( auto itrInner = itr + 1; itrInner != nums.end(); ++itrInner ) { if( (*itr) + (*itrInner) == target ) { vecResult.push_back( i ); vecResult.push_back( j ); return vecResult; } ++j; } ++i; } return vecResult; } };
在寫代碼的時候我們就應該知道迭代器在這種查找下標的場合不太適用。
我們不得不定義兩個變量i和j來記錄下標
事實也正是這樣，當我們submit代碼的時候被拒絕了，原因是在大的數據集面前消耗了過長的時間。
好吧，目前看來我們會的也就這麼多了。
真的是這樣嗎？還有沒有其他方法沒想到？再仔細看看筆記？
大家有沒有嘗試過把入參修改一下呢？
vector<int> twoSum(const vector<int> &nums, const int &target)
有沒有不需要兩個循環就能解決的辦法呢？
如果自己實在想不出來，可以去討論區看看別人的解法
https://discuss.leetcode.com/category/9/two-sum
如果大家其他的解法歡迎隨時和我討論，也可以加入學習群一起交流（公眾號底部菜單）。