LeetCode 001 – Two Sum 筆記

LeetCode 001 – Two Sum

　　發現當了好多年的軟體工程師從來沒寫過 Leet Code（歐美軟體工作人面試題庫），決定加減刷一下，順便記錄一下自己不成熟的思考過程，至於什麼複雜度分析的就不做了，能夠寫得出來就很好了。（以下使用 C++ 語言練習，會先自己隨意寫一遍，然後再參考解答優化。）

　　題目：1. Two Sum
　　連結：https://leetcode.com/problems/two-sum/

　　題目大致的意思說，傳進一組數字組合，跟一個目標值，數字組中會有兩個數相加會等於目標（只會剛好有兩個，也就是說每個題目只會有一組解），要寫程式把那兩個數字在數組中的位置回傳出來，題目自己舉的例子還蠻清楚的，可以參考。

Example:

　　我寫了兩遍才完全弄對。

搞剛法：

　　一開始我搞錯題目意思了，我以為不會有兩個相同的數字出現在數組裡，想說反正兩個目標值不是大於就是小於目標的一半（兩個都小於一半或兩個都大於一半的話加起來不可能等於目標），所以很搞剛的先把數組分成大於一半跟小於一半的兩種，然後用一個當基底掃描另外一組做檢查，在我的想像裡，這應該比全部掃描一遍檢查快一點。

class Solution{
public:

vector<int> twoSum(vector<int>& nums, int target)
{
　　vector<int> ret;

　　if( nums.size() == 0 ) return ret;

　　vector<pair<int, int>> overHalf, lessHalf, equal;
　　int halfTarget = target / 2;

　　bool isTargerEven = target % 2 == 0;

　　for( int index = 0 ; index < nums.size() ; index++ )
　　{
　　　　if( nums[index] > halfTarget )
　　　　　overHalf.push_back(make_pair( nums[index] ,index) );
　　　　else if( nums[index] < halfTarget )
　　　　　lessHalf.push_back( make_pair( nums[index] ,index) );
　　}

　　int num1, num2;

　　for( int index = 0 ; index < lessHalf.size() ; index++ )
　　{
　　　　for( int j = 0 ; j < overHalf.size() ; j++ )
　　　　{
　　　　　　if( overHalf[j].first + lessHalf[index].first == target)
　　　　　　{
　　　　　　　　ret.push_back( overHalf[j].second);
　　　　　　　　ret.push_back( lessHalf[index].second);
　　　　　　}
　　　 }
　　}

　return ret;
}
};

　　但這很明顯只能處理元素都是正整數而且數組元素不能有重復值，要把所有狀況都寫一個判斷式去檢查顯然非常的蠢，所以最後還是用樸實無華的全掃描來做。


全掃描：

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
　　int *numSet = nums.data();
　　vector<int> ret;

　　for( int i = 0 ; i < nums.size() ; i++)
　　{
　　　　for( int j = i + 1 ; j < nums.size() ; j ++ )
　　　　{
　　　　　　if( numSet[i] + numSet[j] == target)
　　　　　　{
　　　　　　　　ret.push_back(i);
　　　　　　　　ret.push_back(j);
　　　　　　　　return ret;
　　　　　　}
　　　　}
　　}

　return ret;
}
};

網站結果：

　　Runtime: 172 ms, faster than 15.17% of C++ online submissions for Two Sum.
　　Memory Usage: 9.1 MB, less than 100.00% of C++ online submissions for Two Sum.

　　效率不是太好，但至少記憶體消耗的少啊，哈哈哈。

Hash Table：

　　後來我偷看了一下解答，全掃描是基本款，答案說用 Map 之類的雜湊表包起來會跑得比較快。基本的思路是這樣，目標值既然是兩個元素的相合，那麼目標值減去其中一個元素必定等於另一個元素，也就是：Ａ + B = C ==> A = C – B

　　那麼跑一次迴圈，在那個迴圈中做這樣的運算：

　　1. 從數組中取出一個元素，假設是 A。

　　2. 確定 C – A 這個值是否存在於 Map 中。

　　3. 若否把 A 以及 A 在數組中的位置存入 Map。Ａ 為鍵，位置為值。

　　4. 若是的狀況後文詳述。

　　5. 跑下一輪迴圈，取出第二個元素 B。

　　假定我們的目標就是 A + B 。這時 C – B 會等於 A，同時 A 已儲存於 Map 中，所以可以被找到，因此輸出 A 跟 B 的位置就是解答。Map 本身就是一種優化到極致的容器類別（某種二元樹的架構，好像紅黑數吧），所以搜尋起來肯定比掃描來得快，用下面的 Code 跑起來的結果是。

class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) 
{
　　vector<int> solution;

　　map<int, int> comps;

　　for(int i = 0; i < nums.size(); ++i)
　　{
　　　　int comp = target - nums[i];

　　　　if (comps.find(comp) == comps.end())
　　　　　　comps[nums[i]] = i;
　　　　else
　　　　{
　　　　　　solution.push_back(comps[comp]);
　　　　　　solution.push_back(i);
　　　　　　break;
　　　　}
　　}

　　return solution;
}
};

　　Runtime: 8 ms, faster than 94.75% of C++ online submissions for Two Sum.
　　Memory Usage: 11 MB, less than 23.87% of C++ online submissions for Two Sum.

　　快了好多倍呢。

附記：

　　作為題庫的第一題，應該也是最簡單的一題，它的解決率莫名地低，不知道是大家看到都不屑解，還是第一題就放棄。就我的狀況來說，這題至少還能理解它的意圖，希望不要第二題就卡關。

　　研究證實，歡笑可以延壽。換言之，讓你捧腹不已的我的文章可以讓你長命百歲，建議多看。歡迎透過側欄粉絲團或下方作者介紹欄按鈕訂閱我，好文章不漏接，期待與您繼續以文相會。

#程式語言 #C++ #程式設計  #軟體開發 #LeetCode