LeetCode 兩數之和

• 2021 年 8 月 7 日
• 筆記
• 演算法系列

1.兩數之和

LeetCode傳送門

題解

#include <vector>
#include <map>
class Solution {
public:
    std::vector<int>
        twoSum(std::vector<int> & nums, int target)
        {
            std::vector<int> result;
            std::map<int,int> map;
            for(int i=0;i<nums.size();i++)
            {
                if(map.count(target - nums[i]) > 0)
                {
                    result.push_back(map[target - nums[i]]);
                    result.push_back(i);
                    return result;
                }
                map[nums[i]] = i;
            }
            return result;
        }
};

解題思路：

• 首先需要創建一個map哈希表
• 然後利用map的count函數去匹配哈希表中存儲的所有的key，如果匹配不到對應的key就存儲一下
• 如果匹配到了key，就說明已經成功找出了兩個相加等於target的數字了

舉例

數組：nums = [8,2,7,9,10]
參數：target=9
輸出：[1,2]

當for里的i=0的時候，此時執行9-8=1，但是我們的map還是個空哈希表，count肯定不會生效，就會把nums[i]放map里，而map數據如下

當for里的i=1的時候，此時會執行9-2=7，很明顯nums下是有7的，但是我們是通過map的key去查找的，很顯然，count依然不會生效，所以還是會進行存儲操作,此時map數據如下

當for里的i=2的時候，此時會執行9-7=2，執行到這裡的時候，可以看到map內是有2這個key的。所以此時count會i命中判斷。
然後我們取出2對應的V=1，在拿到當前循環的i，就可以正確的得到兩個索引值，然後輸出即可