學(xué)長(zhǎng)說(shuō)的好挠他，“解決焦慮的根本途徑是刷Leetcode”舍哄。
1. 兩數(shù)之和
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target站玄，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)谆沃，并返回他們的數(shù)組下標(biāo)游盲。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案吨瞎。但是痹兜，數(shù)組中同一個(gè)元素不能使用兩遍。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
思路
由于是第一次刷題颤诀，數(shù)據(jù)結(jié)構(gòu)基本都已經(jīng)忘的差不多了字旭，只記得最基礎(chǔ)的樹(shù)、鏈表之流崖叫，此題最關(guān)鍵的是解決如何尋找target - num[i]在nums中的位置遗淳，做題時(shí)沒(méi)想到合適的解決辦法，只能從最暴力的O(n2)下手心傀。
如果將nums中的全部元素求和屈暗，在區(qū)分兩個(gè)相加數(shù)位置 最蠢 的情況下，會(huì)得到一個(gè)N* N的矩陣。在此基礎(chǔ)上养叛，不區(qū)分兩個(gè)加數(shù) 第二蠢 的情況下种呐，只取N* N矩陣的上三角矩陣（右上），會(huì)節(jié)省一半的運(yùn)算量弃甥，但是時(shí)間復(fù)雜度仍然保持在O(n2)爽室。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> ans(2); //此處可以不用額外定義一個(gè)vector
for(int i = 0; i < nums.size()-1; i++){
for(int j = i+1; j < nums.size(); j++){
if(nums[i] + nums[j] == target){
ans = {i, j};
return ans; //return {i, j};
}
}
}
return ans; //return {};
}
};
實(shí)際上這里問(wèn)題的本質(zhì)是尋找一種有鍵值關(guān)系數(shù)據(jù)結(jié)構(gòu)，這里的利用鍵值關(guān)系來(lái)優(yōu)化尋找target - num[i]時(shí)間復(fù)雜度淆攻。之前一直認(rèn)為Python中的字典的鍵值之間沒(méi)有任何關(guān)系阔墩，在此悔過(guò)
Game Changer: Hash Table - 哈希表
哈希表是一種使用哈希函數(shù)組織數(shù)據(jù)，以支持快速插入和搜索的數(shù)據(jù)結(jié)構(gòu)瓶珊。
有兩種不同類型的哈希表：哈希集合和哈希映射啸箫。
哈希集合是集合數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)之一，用于存儲(chǔ)非重復(fù)值艰毒。
哈希映射是映射數(shù)據(jù)結(jié)構(gòu)的實(shí)現(xiàn)之一筐高，用于存儲(chǔ)(key, value)鍵值對(duì)。
在標(biāo)準(zhǔn)模板庫(kù)的幫助下丑瞧，哈希表是易于使用的。大多數(shù)常見(jiàn)語(yǔ)言（如Java蜀肘，C ++ 和 Python）都支持哈希集合和哈希映射绊汹。
作者：力扣 (LeetCode)
鏈接：https://leetcode-cn.com/leetbook/read/hash-table/
來(lái)源：力扣（LeetCode）
著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請(qǐng)聯(lián)系作者獲得授權(quán)扮宠，非商業(yè)轉(zhuǎn)載請(qǐng)注明出處西乖。
