➣ Reading Time: 4 minutes

題目出處

https://leetcode.com/problems/two-sum/

難度

easy

題目分類

Array, HashTable

個人範例解法

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;
    }
};

解法重點

這題主要考的是 DP,
需要先建立一張表
(此處利用 map<int,int>,建立 int -> int 對應的 dict),
利用 「key->value」 的特性保存 「值->index」
因此就能快速反查表得到 index

動態規劃 (Dynamic programming,DP) 可參考:

Reference

 ⭐C++ leetcode 相關文章整理⭐:難度Tag
1.【Leetcode】C++ – [1] Two Sum 個人解法筆記 (內含範例程式碼)#easy#Array #HashTable