傳送門：https://leetcode.com/problems/two-sum/#/description

一、題目描述

Given an array of integers, return indices of the two numbers such that they add up to a specific target.
You may assume that each input would have exactly one solution, and you may not use the same element twice.

二、示例

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

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

---

三、問題描述

給定一個(gè)數(shù)字和一個(gè)目標(biāo)數(shù)字，求出數(shù)組中兩個(gè)數(shù)字之和等于給定的目標(biāo)數(shù)字。
注意：假定每個(gè)數(shù)組中有且只有一組解，不能使用同一個(gè)數(shù)組元素兩次
例如：數(shù)組[2,7,11,15], 目標(biāo)數(shù)字9，因?yàn)閚ums[0] + nums[1] = 9,所以返回[0,1]

四、分析

1、暴力解法

遍歷數(shù)組法，直接遍歷整個(gè)數(shù)組，找到兩個(gè)數(shù)組元素和等于target即可。

2、哈希思想

通過建立 <數(shù)值，下標(biāo)> 的哈希表，每遍歷到一個(gè)元素 i ，就查找所對(duì)應(yīng)的元素 target-i 是否在哈希表中，并且 數(shù)值 i 和 數(shù)值 target - i 不能是同一個(gè)下標(biāo)。

五、實(shí)現(xiàn)

1、暴力解法

==》時(shí)間復(fù)雜度：O(n²)

class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {vector<int> res; for(int i = 0; i < nums.size(); i++){for(int j = i + 1; j < nums.size(); j++){if((nums[i] + nums[j]) == target){res.push_back(i);res.push_back(j);break;}} if(!res.empty())break;} return res;} };

提交結(jié)果

2、哈希法

==》時(shí)間復(fù)雜度：O(n)
==》空間復(fù)雜度：O(n)——哈希表

class Solution { public:vector<int> twoSum(vector<int>& nums, int target) {int i,sum;vector<int> results;map<int, int> hmap;for(i = 0; i < nums.size(); i++){hmap.insert(pair<int, int>(nums[i], i));}for(i = 0; i < nums.size(); i++){if(hmap.count(target - nums[i]) && hmap[target - nums[i]] != i){int n = hmap[target - nums[i]];results.push_back(i);results.push_back(n);break;} }return results;} };

注：使用count，返回的是被查找元素的個(gè)數(shù)。如果有，返回1；否則，返回0。注意，map中不存在相同元素，所以返回值只能是1或0。
提交結(jié)果

六、哈希算法

1、基本概念

哈希算法（也稱散列算法）
將任意長(zhǎng)度的輸入（又叫做預(yù)映射， pre-image）映射為固定長(zhǎng)度的輸出的映射規(guī)則。
==》散列值的空間通常遠(yuǎn)小于輸入的空間

哈希值（也稱散列值）
通過對(duì)原始數(shù)據(jù)映射后得到的輸出。

哈希表
以 鍵-值（key-value） 存儲(chǔ)數(shù)據(jù)的結(jié)構(gòu)，只需輸入待查找的 key，就可以查找其對(duì)應(yīng)的值。

負(fù)載因子
例如要存儲(chǔ)80個(gè)元素，但可能為這80個(gè)元素申請(qǐng)了100個(gè)元素的空間。80/100=0.8，這個(gè)數(shù)字稱為負(fù)載因子。我們之所以這樣做，也是為了“高速存取”的目的。

沖突
兩個(gè)元素通過 哈希函數(shù) 得到同樣的結(jié)果。

2、哈希算法的設(shè)計(jì)要求

• 從哈希值不能反向推導(dǎo)出原始數(shù)據(jù)（所以哈希算法也叫單向哈希算法）；
• 對(duì)輸入數(shù)據(jù)非常敏感，哪怕原始數(shù)據(jù)只修改了一個(gè) Bit，最后得到的哈希值也大不相同；
• 散列沖突的概率要很小，對(duì)于不同的原始數(shù)據(jù)，哈希值相同的概率非常小；
• 哈希算法的執(zhí)行效率要盡量高效，針對(duì)較長(zhǎng)的文本，也能快速地計(jì)算出哈希值。

==》無論哈希文本長(zhǎng)度，都可得到長(zhǎng)度相同的哈希值；
==》兩個(gè)相似的文本，得到的哈希值完全不同。

3、散列函數(shù)設(shè)計(jì)原則

• 散列函數(shù)的設(shè)計(jì)不能太復(fù)雜。否則，消耗很多計(jì)算時(shí)間，間接影響散列表性能。
• 散列函數(shù)生成的值盡可能隨機(jī)且均勻分布==》避免或最小化散列沖突，即便沖突，也比較平均。

散列函數(shù)設(shè)計(jì)方法：數(shù)據(jù)分析法(從原始數(shù)據(jù)中截取部分作為散列函數(shù))、直接尋址法、平方取中法、折疊法、隨機(jī)數(shù)法等

4、常見散列函數(shù)的構(gòu)建方法

• 直接尋址法：取keyword或keyword的某個(gè)線性函數(shù)值為散列地址。即H(key)=key或H(key) = a?key + b，當(dāng)中a和b為常數(shù)（這樣的散列函數(shù)叫做自身函數(shù)）
• 數(shù)字分析法：分析一組數(shù)據(jù)，比方一組員工的出生年月日，這時(shí)我們發(fā)現(xiàn)出生年月日的前幾位數(shù)字大體同樣，這種話，出現(xiàn)沖突的幾率就會(huì)非常大，可是我們發(fā)現(xiàn)年月日的后幾位表示月份和詳細(xì)日期的數(shù)字區(qū)別非常大，假設(shè)用后面的數(shù)字來構(gòu)成散列地址，則沖突的幾率會(huì)明顯減少。因此數(shù)字分析法就是找出數(shù)字的規(guī)律，盡可能利用這些數(shù)據(jù)來構(gòu)造沖突幾率較低的散列地址。
• 平方取中法：取keyword平方后的中間幾位作為散列地址
• 折疊法：將keyword切割成位數(shù)同樣的幾部分，最后一部分位數(shù)能夠不同，然后取這幾部分的疊加和（去除進(jìn)位）作為散列地址。
• 隨機(jī)數(shù)法：選擇一隨機(jī)函數(shù)，取keyword的隨機(jī)值作為散列地址，通經(jīng)常使用于keyword長(zhǎng)度不同的場(chǎng)合。
• 除留余數(shù)法：取keyword被某個(gè)不大于散列表表長(zhǎng)m的數(shù)p除后所得的余數(shù)為散列地址。即 H(key) = key MOD p, p<=m。不僅能夠?qū)eyword直接取模，也可在折疊、平方取中等運(yùn)算之后取模。對(duì)p的選擇非常重要，一般取素?cái)?shù)或m，若p選的不好，easy產(chǎn)生同義詞。

5、散列沖突

兩類方法：開放尋址法（open addressing）和鏈表法（chaining）

（1）開放尋址法

基本思想： 若存在散列沖突，則探測(cè)一個(gè)空閑位置，將其插入。

A、探測(cè)方法

① 線性探測(cè)（Linear Probing）
從當(dāng)前位置開始，依次往后（若不夠則從頭繼續(xù)）查找，看是否有空閑位置，直到找到為止。

② 二次探測(cè)（Quadratic Probing）
區(qū)別： 步長(zhǎng)變成了原來的“二次方“，即：探測(cè)的下標(biāo)序列
hash(key)+0，hash(key)+1²，hash(key)+2²，hash(key)+3²,……

③ 雙重散列（Double hashing）
使用一組散列函數(shù) hash1(key)，hash2(key)，hash3(key)……先用第一個(gè)散列函數(shù)，如果計(jì)算得到的存儲(chǔ)位置已經(jīng)被占用，再用第二個(gè)散列函數(shù)，依次類推，直到找找到空閑的存儲(chǔ)位置。

B、存在問題

當(dāng)數(shù)據(jù)越來越多時(shí)，散列沖突發(fā)生的可能性就會(huì)越來越大，空閑位置會(huì)越來越少，線性探測(cè)的時(shí)間就會(huì)越來越久。極端情況下，最壞情況下的時(shí)間復(fù)雜度為 O(n)。同理，在刪除和查找時(shí)，，也有可能會(huì)線性探測(cè)整張散列表，才能找到要查找或者刪除的數(shù)據(jù)。

C、裝載因子（load factor）

為了盡可能保證散列表的操作效率，利用裝載因子（load factor）來表示空閑槽位的多少。

散列表的裝載因子 = 填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度

裝載因子越大，說明空閑位置越少，沖突越多，散列表的性能會(huì)下降。

（2）鏈表法——更常用

所有散列值相同的元素我們都放到相同槽位對(duì)應(yīng)的鏈表中。

插入：通過散列函數(shù)計(jì)算出對(duì)應(yīng)的散列槽位，將其插入到對(duì)應(yīng)鏈表中即可
==》時(shí)間復(fù)雜度：O(1)
查找、刪除：需要遍歷，時(shí)間復(fù)雜度跟鏈表的長(zhǎng)度 k 成正比，也就是 O(k)。

對(duì)于散列比較均勻的散列函數(shù)來說，理論上講，k=n/m，其中 n 表示散列中數(shù)據(jù)的個(gè)數(shù)，m 表示散列表中“槽”的個(gè)數(shù)。

6、應(yīng)用

最常見的幾種應(yīng)用：安全加密、唯一標(biāo)識(shí)、數(shù)據(jù)校驗(yàn)、散列函數(shù)、負(fù)載均衡、數(shù)據(jù)分片、分布式存儲(chǔ)。

總結(jié)

以上是生活随笔為你收集整理的【编程1】 Two Sum + 哈希算法的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。