題目出處
https://leetcode.com/problems/two-sum/
難度
easy
題目分類
Array, HashTable
個人範例解法 – 一刷 (2021/10/18)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int,int> dict;
map<int,int>::iterator iter;
vector<int> ans;
for (int i=0; i<nums.size();i++){
iter = dict.find(target-nums[i]);
// cout<<iter;
// printf("(%d,%d)",iter->first,iter->second);
if (iter != dict.end()){ // num found
ans.push_back(iter->second); //nums find in dict (smaller)
ans.push_back(i); // current index (bigger)
return ans;
}
else{ //iter == dict.end(), not found
dict[nums[i]]=i;
}
}
return ans;
}
};
個人範例解法 – 二刷 (2022/02/24)
第二次要順便複習一下如何找 map 的 keys 的方法
(python 寫太多都忘了)
補充附於文末
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
map<int, int> mymap;
vector<int> ans;
for(int i=0; i < nums.size(); i++){
if(mymap.find(nums[i]) != mymap.end()){ // found
ans.push_back(mymap[nums[i]]);
ans.push_back(i);
return ans;
}
else{
mymap[target - nums[i]] = i;
}
}
return ans;
}
};
解法重點
這題主要考的是 DP,
需要先建立一張表
(此處利用 map<int,int>,建立 int -> int 對應的 dict),
利用 「key->value」 的特性保存 「值->index」
因此就能快速反查表得到 index
動態規劃 (Dynamic programming,DP) 可參考:
map find 的方法
被 python 寵壞的我,整個 dict find 了起來 Orz
來我們回到一下 C++ map 的世界。
根據 iterator 找到元素
既然是特殊的資料型態,我們自然要靠 iterator 來幫助我們遍歷一下,
思考的方式很簡單,iterator 會幫助我們一直看資料,
那什麼情況會一直看到最後呢?
就是「沒找到」的時候啦!!!
map<int, int> mymap;
if(mymap.find(nums[i]) != mymap.end()){
// found
}
else{
// not found
}
或不喜歡逆邏輯 (使用’不等於’符號) 的人,我們也可以正向的來
map<int, int> mymap;
if(mymap.find(nums[i]) == mymap.end()){
// not found
}
else{
// found
}
Reference
⭐ Leetcode 解題紀錄 ⭐ | 題型 | 資料結構 | Python Solution | C++ Solution | Note | |
---|---|---|---|---|---|---|
⭐BFS 相關題型 ⭐ | ||||||
104 | Maximum Depth of Binary Tree | BFS (分層) | Python | |||
94 | Binary Tree Inorder Traversal | BFS (分層) | Tree | Python | 內含 處理 Tree 樹問題的重點 | |
102 | Binary Tree Level Order Traversal | BFS (分層) | Tree | Python | ||
103 | Binary Tree Zigzag Level Order Traversal |