Press "Enter" to skip to content

LeetCode 001 – Two Sum 筆記

 161 total views,  10 views today

LeetCode 001 – Two Sum

LeetCode 001 – Two Sum 筆記

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

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

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

Example:

範例

  Given nums = [2, 7, 11, 15], target = 9,

  Because nums[0] + nums[1] = 2 + 7 = 9,

  return [0, 1]

  我寫了兩遍才完全弄對。

搞剛法:

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

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 之類的雜湊表包起來會跑得比較快。基本的思路是這樣,目標值既然是兩個元素的相合,那麼目標值減去其中一個元素必定等於另一個元素,也就是:A + B = C ==> A = C – B

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

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

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

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

  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 

好文章應與世界一同分享

Leave a Reply