大家一起學AI

實現Leetcode1-Two Sum，該例題之問題如以下所示，有一個Vector中包含數個元素(2、7、11、15)，且給一個目標值9，試問該向量中哪兩個元素值相加為此目標值，並回傳此向量中那兩個元素之索引值，以下例子中9為2+7，因此回傳索引值為0以及1。

Example:

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

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

作法解析:透過建立Hash table的方式，可以有效率的實現此問題。

程式碼:

class Solution {
public:
    vector twoSum(vector& nums, int target) {   
        vector answer; //宣告一個要回傳的vector
        unordered_map m; //宣告一個hasing map型態
        int tmp; 
        for (int i = 0; i < nums.size(); i++) 
        {
            tmp = target - nums[i]; //計算目前元素與目標之差值
            if (m.count(tmp) && m[tmp] != i)  //判斷該差值是否存在以及防止兩個元素相同
            {
                answer.push_back(m[tmp]);  //將索引值放入vector中並跳出
                answer.push_back(i);
                break;
            }
            m[nums[i]] = i;  //將數值以及索引值放入hasing map中
        }
        
        return answer;
    }
};

程式解析:

1.建立出之hash table如以下所示。

2.透過使用m.count(tmp)來判斷該差值是否存在hash table中，舉例來說，若差值為2則回傳索引值為0、差值為7則回傳1，以此類推。