散列表概念
散列表（Hash table盛嘿，也叫哈希表）娜饵，是根據(jù)鍵（Key）而直接訪問在內(nèi)存存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)。也就是說(shuō)小染，它通過(guò)計(jì)算一個(gè)關(guān)于鍵值的函數(shù)翘瓮，將所需查詢的數(shù)據(jù)映射到表中一個(gè)位置來(lái)訪問記錄，這加快了查找速度裤翩。這個(gè)映射函數(shù)稱做散列函數(shù)资盅，存放記錄的數(shù)組稱做散列表。
更加詳細(xì)的介紹請(qǐng)戳這：
1. 兩數(shù)之和
題目來(lái)源于 LeetCode 上第 1 號(hào)問題： Two Sum踊赠。
題目描述
給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)目標(biāo)值 target呵扛，請(qǐng)你在該數(shù)組中找出和為目標(biāo)值的那 兩個(gè) 整數(shù)，并返回他們的數(shù)組下標(biāo)臼疫。
你可以假設(shè)每種輸入只會(huì)對(duì)應(yīng)一個(gè)答案择份。但是，你不能重復(fù)利用這個(gè)數(shù)組中同樣的元素烫堤。
示例:
給定 nums = [2, 7, 11, 15], target = 9
因?yàn)?nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
題目解析
使用散列表來(lái)解決該問題。
首先設(shè)置一個(gè) map 容器 record 用來(lái)記錄元素的值與索引凤价，然后遍歷數(shù)組 nums 鸽斟。
- 每次遍歷時(shí)使用臨時(shí)變量 complement 用來(lái)保存目標(biāo)值與當(dāng)前值的差值
- 在此次遍歷中查找 record ，查看是否有與 complement 一致的值利诺，如果查找成功則返回查找值的索引值與當(dāng)前變量的值i
- 如果未找到富蓄，則在 record 保存該元素與索引值 i
動(dòng)畫描述
代碼實(shí)現(xiàn)
// 1. Two Sum
// 時(shí)間復(fù)雜度：O(n)
// 空間復(fù)雜度：O(n)
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> record;
for(int i = 0 ; i < nums.size() ; i ++){
int complement = target - nums[i];
if(record.find(complement) != record.end()){
int res[] = {i, record[complement]};
return vector<int>(res, res + 2);
}
record[nums[i]] = i;
}
}
};
2. 無(wú)重復(fù)字符的最長(zhǎng)子串
題目來(lái)源于 LeetCode 上第 3 號(hào)問題： Longest Substring Without Repeating Characters 。
題目描述
給定一個(gè)字符串慢逾，請(qǐng)你找出其中不含有重復(fù)字符的 最長(zhǎng)子串 的長(zhǎng)度立倍。
題目解析
建立一個(gè) HashMap 灭红，建立每個(gè)字符和其最后出現(xiàn)位置之間的映射，然后再定義兩個(gè)變量 res 和 left 口注，其中 res 用來(lái)記錄最長(zhǎng)無(wú)重復(fù)子串的長(zhǎng)度变擒，left 指向該無(wú)重復(fù)子串左邊的起始位置的前一個(gè)，一開始由于是前一個(gè)寝志，所以在初始化時(shí)就是 -1娇斑。
接下來(lái)遍歷整個(gè)字符串，對(duì)于每一個(gè)遍歷到的字符材部，如果該字符已經(jīng)在 HashMap 中存在了毫缆，并且如果其映射值大于 left 的話，那么更新 left 為當(dāng)前映射值乐导，然后映射值更新為當(dāng)前坐標(biāo)i苦丁，這樣保證了left始終為當(dāng)前邊界的前一個(gè)位置，然后計(jì)算窗口長(zhǎng)度的時(shí)候物臂，直接用 i-left 即可旺拉，用來(lái)更新結(jié)果 res 。
代碼實(shí)現(xiàn)
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0, left = -1, n = s.size();
unordered_map<int, int> m;
for (int i = 0; i < n; ++i) {
if (m.count(s[i]) && m[s[i]] > left) {
left = m[s[i]];
}
m[s[i]] = i;
res = max(res, i - left);
}
return res;
}
};
拓展
此題也可以使用滑動(dòng)窗口的概念來(lái)處理鹦聪。
建立一個(gè) 256 位大小的整型數(shù)組 freg 账阻，用來(lái)建立字符和其出現(xiàn)位置之間的映射。
維護(hù)一個(gè)滑動(dòng)窗口泽本，窗口內(nèi)的都是沒有重復(fù)的字符淘太，去盡可能的擴(kuò)大窗口的大小，窗口不停的向右滑動(dòng)规丽。
- （1）如果當(dāng)前遍歷到的字符從未出現(xiàn)過(guò)蒲牧，那么直接擴(kuò)大右邊界；
- （2）如果當(dāng)前遍歷到的字符出現(xiàn)過(guò)赌莺，則縮小窗口（左邊索引向右移動(dòng)）冰抢，然后繼續(xù)觀察當(dāng)前遍歷到的字符；
- （3）重復(fù)（1）（2）艘狭，直到左邊索引無(wú)法再移動(dòng)挎扰；
- （4）維護(hù)一個(gè)結(jié)果 res，每次用出現(xiàn)過(guò)的窗口大小來(lái)更新結(jié)果 res 巢音，最后返回 res 獲取結(jié)果遵倦。
動(dòng)畫描述
代碼實(shí)現(xiàn)
// 3. Longest Substring Without Repeating Characters
// 滑動(dòng)窗口
// 時(shí)間復(fù)雜度: O(len(s))
// 空間復(fù)雜度: O(len(charset))
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int freq[256] = {0};
int l = 0, r = -1; //滑動(dòng)窗口為s[l...r]
int res = 0;
// 整個(gè)循環(huán)從 l == 0; r == -1 這個(gè)空窗口開始
// 到l == s.size(); r == s.size()-1 這個(gè)空窗口截止
// 在每次循環(huán)里逐漸改變窗口, 維護(hù)freq, 并記錄當(dāng)前窗口中是否找到了一個(gè)新的最優(yōu)值
while(l < s.size()){
if(r + 1 < s.size() && freq[s[r+1]] == 0){
r++;
freq[s[r]]++;
}else { //r已經(jīng)到頭 || freq[s[r+1]] == 1
freq[s[l]]--;
l++;
}
res = max(res, r-l+1);
}
return res;
}
};
3. 三數(shù)之和
題目來(lái)源于 LeetCode 上第 15 號(hào)問題： 3Sum 。
題目描述
給定一個(gè)包含 n 個(gè)整數(shù)的數(shù)組 nums官撼，判斷 nums 中是否存在三個(gè)元素 a梧躺，b，c 傲绣，使得 a + b + c = 0 掠哥？找出所有滿足條件且不重復(fù)的三元組巩踏。
題目解析
題目需要我們找出三個(gè)數(shù)且和為 0 ，那么除了三個(gè)數(shù)全是 0 的情況之外续搀，肯定會(huì)有負(fù)數(shù)和正數(shù)塞琼，所以一開始可以先選擇一個(gè)數(shù)，然后再去找另外兩個(gè)數(shù)目代，這樣只要找到兩個(gè)數(shù)且和為第一個(gè)選擇的數(shù)的相反數(shù)就行了屈梁。也就是說(shuō)需要枚舉 a 和 b ，將 c 的存入 map 即可榛了。
需要注意的是返回的結(jié)果中在讶，不能有有重復(fù)的結(jié)果。這樣的代碼時(shí)間復(fù)雜度是 O(n^2)霜大。在這里可以先將原數(shù)組進(jìn)行排序构哺，然后再遍歷排序后的數(shù)組，這樣就可以使用雙指針以線性時(shí)間復(fù)雜度來(lái)遍歷所有滿足題意的兩個(gè)數(shù)組合战坤。
代碼實(shí)現(xiàn)
class Solution {
public:
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> res;
sort(nums.begin(), nums.end());
if (nums.empty() || nums.back() < 0 || nums.front() > 0) return {};
for (int k = 0; k < nums.size(); ++k) {
if (nums[k] > 0) break;
if (k > 0 && nums[k] == nums[k - 1]) continue;
int target = 0 - nums[k];
int i = k + 1, j = nums.size() - 1;
while (i < j) {
if (nums[i] + nums[j] == target) {
res.push_back({nums[k], nums[i], nums[j]});
while (i < j && nums[i] == nums[i + 1]) ++i;
while (i < j && nums[j] == nums[j - 1]) --j;
++i; --j;
} else if (nums[i] + nums[j] < target) ++i;
else --j;
}
}
return res;
}
};
4. 重復(fù)的 DNA 序列
題目來(lái)源于 LeetCode 上第 187 號(hào)問題： Repeated DNA Sequences 曙强。
題目描述
所有 DNA 由一系列縮寫為 A，C途茫，G 和 T 的核苷酸組成碟嘴，例如：“ACGAATTCCG”。在研究 DNA 時(shí)囊卜，識(shí)別 DNA 中的重復(fù)序列有時(shí)會(huì)對(duì)研究非常有幫助娜扇。
編寫一個(gè)函數(shù)來(lái)查找 DNA 分子中所有出現(xiàn)超過(guò)一次的 10 個(gè)字母長(zhǎng)的序列（子串）。
題目解析
首先栅组，先將 A , C , G , T 的 ASCII 碼用二進(jìn)制來(lái)表示：
A: 0100 0001 C: 0100 0011 G: 0100 0111 T: 0101 0100
通過(guò)觀察發(fā)現(xiàn)每個(gè)字符的后三位都不相同雀瓢，因此可以用末尾的三位來(lái)區(qū)分這四個(gè)字符。
題目要求是查找 10 個(gè)字母長(zhǎng)的序列玉掸，這里我們將每個(gè)字符用三位來(lái)區(qū)分的話刃麸，10 個(gè)字符就需要 30 位 ，在32位機(jī)上也 OK 司浪。
為了提取出后 30 位泊业，需要使用 mask ，取值為 0x7ffffff（二進(jìn)制表示含有 27 個(gè) 1） 啊易，先用此 mask 可取出整個(gè)序列的后 27 位脱吱，然后再向左平移三位可取出 10 個(gè)字母長(zhǎng)的序列 （ 30 位）。
為了保存子串的頻率认罩，這里使用哈希表。
首先當(dāng)取出第十個(gè)字符時(shí)续捂，將其存在哈希表里垦垂，和該字符串出現(xiàn)頻率映射宦搬，之后每向左移三位替換一個(gè)字符，查找新字符串在哈希表里出現(xiàn)次數(shù)劫拗，如果之前剛好出現(xiàn)過(guò)一次间校，則將當(dāng)前字符串存入返回值的數(shù)組并將其出現(xiàn)次數(shù)加一，如果從未出現(xiàn)過(guò)页慷，則將其映射到 1憔足。
解題代碼
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
vector<string> res;
if (s.size() <= 10) return res;
int mask = 0x7ffffff, cur = 0;
unordered_map<int, int> m;
for (int i = 0; i < 9; ++i) {
cur = (cur << 3) | (s[i] & 7);
}
for (int i = 9; i < s.size(); ++i) {
cur = ((cur & mask) << 3) | (s[i] & 7);
if (m.count(cur)) {
if (m[cur] == 1) res.push_back(s.substr(i - 9, 10));
++m[cur];
} else {
m[cur] = 1;
}
}
return res;
}
};
5. 兩個(gè)數(shù)組的交集
題目來(lái)源于 LeetCode 上第 349 號(hào)問題： Intersection of Two Arrays。
題目描述
給定兩個(gè)數(shù)組酒繁，編寫一個(gè)函數(shù)來(lái)計(jì)算它們的交集滓彰。
題目解析
容器類 set 的使用。
- 遍歷 num1州袒，通過(guò) set 容器 record 存儲(chǔ) num1 的元素
- 遍歷 num2揭绑，在 record 中查找是否有相同的元素，如果有郎哭，用 set 容器 resultSet 進(jìn)行存儲(chǔ)
- 將 resultSet 轉(zhuǎn)換為 vector 類型
動(dòng)畫描述
代碼實(shí)現(xiàn)
// 時(shí)間復(fù)雜度: O(nlogn)
// 空間復(fù)雜度: O(n)
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
set<int> record;
for( int i = 0 ; i < nums1.size() ; i ++ ){
record.insert(nums1[i]);
}
set<int> resultSet;
for( int i = 0 ; i < nums2.size() ; i ++ ){
if(record.find(nums2[i]) != record.end()){
resultSet.insert(nums2[i]);
}
}
vector<int> resultVector;
for(set<int>::iterator iter = resultSet.begin(); iter != resultSet.end(); iter ++ ){
resultVector.push_back(*iter);
}
return resultVector;
}
};
6. 兩個(gè)數(shù)組的交集 II
題目來(lái)源于 LeetCode 上第 350 號(hào)問題： Intersection of Two Arrays II他匪。
題目描述
給定兩個(gè)數(shù)組，編寫一個(gè)函數(shù)來(lái)計(jì)算它們的交集夸研。
示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
題目解析
與上題 兩個(gè)數(shù)組的交集 類似邦蜜。只不過(guò)這里使用的是 map 。
- 遍歷 num1亥至，通過(guò) map 容器 record 存儲(chǔ) num1 的元素與頻率悼沈；
- 遍歷 num2 ，在 record 中查找是否有相同的元素（該元素的存儲(chǔ)頻率大于 0 ）抬闯，如果有井辆，用 map 容器resultVector 進(jìn)行存儲(chǔ)，同時(shí)該元素的頻率減一溶握。
動(dòng)畫描述
代碼實(shí)現(xiàn)
// 時(shí)間復(fù)雜度: O(nlogn)
// 空間復(fù)雜度: O(n)
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
map<int, int> record;
for(int i = 0 ; i < nums1.size() ; i ++){
record[nums1[i]] += 1;
}
vector<int> resultVector;
for(int i = 0 ; i < nums2.size() ; i ++){
if(record[nums2[i]] > 0){
resultVector.push_back(nums2[i]);
record[nums2[i]] --;
}
}
return resultVector;
}
};
7. 回旋鏢的數(shù)量
題目來(lái)源于 LeetCode 上第 447 號(hào)問題： Number of Boomerangs 杯缺。
題目描述
給定平面上 n 對(duì)不同的點(diǎn)，“回旋鏢” 是由點(diǎn)表示的元組 (i, j, k) 睡榆，其中 i 和 j 之間的距離和 i 和 k 之間的距離相等（需要考慮元組的順序）萍肆。
找到所有回旋鏢的數(shù)量。你可以假設(shè) n 最大為 500胀屿，所有點(diǎn)的坐標(biāo)在閉區(qū)間 [-10000, 10000] 中塘揣。
題目解析
n 最大為 500，可以使用時(shí)間復(fù)雜度為 O(n^2)的算法宿崭。
- 遍歷所有的點(diǎn)亲铡，讓每個(gè)點(diǎn)作為一個(gè)錨點(diǎn)
- 然后再遍歷其他的點(diǎn)，統(tǒng)計(jì)和錨點(diǎn)距離相等的點(diǎn)有多少個(gè)
- 然后分別帶入 n(n-1) 計(jì)算結(jié)果并累加到 res 中
注意點(diǎn)：
如果有一個(gè)點(diǎn)a，還有兩個(gè)點(diǎn) b 和 c 奖蔓，如果 ab 和 ac 之間的距離相等赞草，那么就有兩種排列方法 abc 和 acb ；
如果有三個(gè)點(diǎn)b吆鹤，c厨疙，d 都分別和 a 之間的距離相等，那么有六種排列方法疑务，abc, acb, acd, adc, abd, adb沾凄；
如果有 n 個(gè)點(diǎn)和點(diǎn) a 距離相等，那么排列方式為 n(n-1)知允；
計(jì)算距離時(shí)不進(jìn)行開根運(yùn)算, 以保證精度撒蟀；
只有當(dāng) n 大于等于 2 時(shí)，res 值才會(huì)真正增加廊镜，因?yàn)楫?dāng)n=1時(shí)牙肝，增加量為
1 * ( 1 - 1 ) = 0。
動(dòng)畫描述
代碼實(shí)現(xiàn)
// 時(shí)間復(fù)雜度: O(n^2)
// 空間復(fù)雜度: O(n)
class Solution {
public:
int numberOfBoomerangs(vector<pair<int, int>>& points) {
int res = 0;
for( int i = 0 ; i < points.size() ; i ++ ){
// record中存儲(chǔ) 點(diǎn)i 到所有其他點(diǎn)的距離出現(xiàn)的頻次
unordered_map<int, int> record;
for(int j = 0 ; j < points.size() ; j ++){
if(j != i){
// 計(jì)算距離時(shí)不進(jìn)行開根運(yùn)算, 以保證精度
record[dis(points[i], points[j])] += 1;
}
}
for(unordered_map<int, int>::iterator iter = record.begin() ; iter != record.end() ; iter ++){
res += (iter->second) * (iter->second - 1);
}
}
return res;
}
private:
int dis(const pair<int,int> &pa, const pair<int,int> &pb){
return (pa.first - pb.first) * (pa.first - pb.first) +
(pa.second - pb.second) * (pa.second - pb.second);
}
};
8. 四數(shù)相加 II
題目來(lái)源于 LeetCode 上第 454 號(hào)問題： 4Sum II 嗤朴。
題目描述
給定四個(gè)包含整數(shù)的數(shù)組列表 A , B , C , D ,計(jì)算有多少個(gè)元組 (i, j, k, l) 配椭，使得 A[i] + B[j] + C[k] + D[l] = 0。
為了使問題簡(jiǎn)單化雹姊，所有的 A, B, C, D 具有相同的長(zhǎng)度 N股缸，且 0 ≤ N ≤ 500 。所有整數(shù)的范圍在 -2^28 到 2^28- 1 之間吱雏，最終結(jié)果不會(huì)超過(guò) 2^31 - 1 敦姻。
題目解析
與 Two Sum 極其類似，使用哈希表來(lái)解決問題歧杏。
- 把 A 和 B 的兩兩之和都求出來(lái)镰惦，在哈希表中建立兩數(shù)之和與其出現(xiàn)次數(shù)之間的映射；
- 遍歷 C 和 D 中任意兩個(gè)數(shù)之和犬绒，只要看哈希表存不存在這兩數(shù)之和的相反數(shù)就行了旺入。
動(dòng)畫描述
代碼實(shí)現(xiàn)
// 時(shí)間復(fù)雜度: O(n^2)
// 空間復(fù)雜度: O(n^2)
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
unordered_map<int,int> hashtable;
for(int i = 0 ; i < A.size() ; i ++){
for(int j = 0 ; j < B.size() ; j ++){
hashtable[A[i]+B[j]] += 1;
}
}
int res = 0;
for(int i = 0 ; i < C.size() ; i ++){
for(int j = 0 ; j < D.size() ; j ++){
if(hashtable.find(-C[i]-D[j]) != hashtable.end()){
res += hashtable[-C[i]-D[j]];
}
}
}
return res;
}
};
