代碼隨想錄：哈希表
哈希表是根據(jù)關(guān)鍵碼的值直接訪問(wèn)數(shù)據(jù)的數(shù)據(jù)結(jié)構(gòu)，可以根據(jù)一個(gè)key直接訪問(wèn)數(shù)據(jù)
哈希表一般用來(lái)快速判斷一個(gè)元素是否出現(xiàn)在集合中
查詢一個(gè)學(xué)生是否在學(xué)校名單上枚舉的話時(shí)間復(fù)雜度為O(n)，用哈希表時(shí)間復(fù)雜度為O(1)
將學(xué)生的名字映射到哈希表上就涉及到哈希函數(shù)，哈希函數(shù)是通過(guò)hashCode通過(guò)特定編碼方式將其他數(shù)據(jù)轉(zhuǎn)化為不同數(shù)值
為了保證映射出來(lái)的索引數(shù)值都落在哈希表上，對(duì)數(shù)值進(jìn)行一個(gè)取模操作保證所有數(shù)據(jù)都可以映射到哈希表
哈希碰撞：兩個(gè)數(shù)據(jù)映射到哈希表同一索引位置，此現(xiàn)象即為哈希碰撞，解決辦法一般有兩種，拉鏈法和線性探測(cè)法
拉鏈法，在某一索引位置發(fā)生沖突的元素全部存儲(chǔ)到鏈表中，要適當(dāng)選擇哈希表的大小防止因數(shù)組空值浪費(fèi)內(nèi)存或因鏈表太長(zhǎng)在查找上浪費(fèi)時(shí)間
線性探測(cè)法（*要求tableSize>dataSize)依靠哈希表中的空位解決問(wèn)題，沖突位置已經(jīng)存放了一個(gè)信息就向下找一個(gè)空位存放新的信息
常見(jiàn)的三種哈希結(jié)構(gòu)：數(shù)組，set（集合），map（映射）（c#中對(duì)應(yīng)Dictionary）
當(dāng)我們需要快速判斷一個(gè)元素是否出現(xiàn)在集合中時(shí)考慮使用哈希法，哈希法犧牲空間換取時(shí)間
力扣242：有效的字母異位詞
public?class?Solution?{
????public?bool?IsAnagram(string?s,?string?t)?{
????????int[]?rec=new?int[26];
//要求只有小寫(xiě)字母因此建立長(zhǎng)度為26的數(shù)組
????????for(int?i=0;i<s.Length;i++){
????????????rec[s[i]-'a']++;
//把每次s中出現(xiàn)的字母對(duì)應(yīng)的元素+1
????????}
????????for(int?j=0;j<t.Length;j++){
????????????rec[t[j]-'a']--;
//每次t中出現(xiàn)的字母對(duì)應(yīng)元素-1
????????}
????????for(int?k=0;k<26;k++){
????????????if(rec[k]!=0){
????????????????return?false;
//若有元素不是0說(shuō)明s和t字符不一樣，返回false
????????????}
????????}
????????return?true;
????}
}
力扣349：兩個(gè)數(shù)組的交集
public?class?Solution?{
????public?int[]?Intersection(int[]?nums1,?int[]?nums2)?{
????????HashSet<int>?hs1?=?new?HashSet<int>(nums1);
????????HashSet<int>?r=new?HashSet<int>();
????????foreach(int?n?in?nums2){
????????????if(hs1.Contains(n)){
????????????????r.Add(n);
//將其中一個(gè)數(shù)組放進(jìn)集合里，遍歷另一個(gè)數(shù)組尋找集合中有無(wú)重復(fù)數(shù)字，有就添加到保存結(jié)果的集合里
????????????}
????????}
??????return?r.ToArray();
//結(jié)果集合轉(zhuǎn)化成數(shù)組
????}
}
力扣1：兩數(shù)之和
?public?class?Solution?{
????public?int[]?TwoSum(int[]?nums,?int?target)?{
????????Dictionary<int,int>?map=new?Dictionary<int,?int>();
????????int[]?rsl?=?new?int[2];
????????for?(int?i?=?0;?i?<?nums.Length;?i++)
????????{
????????????int?a?=?target?-?nums[i];
????????????if?(map.ContainsKey(a))
????????????{
????????????????rsl[0]?=?i;
????????????????rsl[1]?=?map[a];
//一邊遍歷一邊填表，在表格中找符合條件的數(shù)
????????????}
????????????????if(!map.TryAdd(nums[i],i)){
????????????????????map[a]=i;
//根據(jù)TryAdd的返回值判斷有無(wú)重復(fù)數(shù)字決定是否更新map中的value位置
????????????????}
????????????
????????}
????????return?rsl;
????}
}
力扣454：四數(shù)之和II
public?class?Solution?{
????public?int?FourSumCount(int[]?nums1,?int[]?nums2,?int[]?nums3,?int[]?nums4)?{
????????Dictionary<int,int?>?map=?new?Dictionary<int,?int>();
????????foreach?(int?a?in?nums1)
????????{
????????????foreach?(int?b?in?nums2)
????????????{
????????????????map.TryAdd(a+b,0);
//建立的map中初始化以后為空，第一次需要手動(dòng)填入key和value
????????????????map[a?+?b]++;
//統(tǒng)計(jì)a+b結(jié)果出現(xiàn)的次數(shù)作為value
????????????}
????????}
????????int?count?=?0;
????????foreach?(int?c?in?nums3)
????????{
????????????foreach?(int?d?in?nums4)
????????????{
????????????????if?(map.ContainsKey(0-c-d))
????????????????{
????????????????????count?+=?map[0?-?c?-?d];
//統(tǒng)計(jì)0-c-d的結(jié)果在map中出現(xiàn)的次數(shù)再與count自身相加即為所求結(jié)果
????????????????}
????????????}
????????}
????????return?count;
????}
}
力扣15：三數(shù)之和
public?class?Solution?{
???public?IList<IList<int>>?ThreeSum(int[]?nums)
????{
????????IList<IList<int>>?result?=?new?List<IList<int>>();
????????Array.Sort(nums);
????????for?(int?i?=?0;?i?<?nums.Length;?i++)
????????{
????????????if?(nums[i]>0)
????????????{
????????????????break;
//若排序后第一個(gè)數(shù)字大于0則停止尋找
????????????}
????????????if?(i>0&&nums[i]==nums[i-1])
????????????{
????????????????continue;
//若i重復(fù)則進(jìn)行下一次循環(huán)
????????????}
????????????HashSet<int>?set?=?new?HashSet<int>();
//靠每次循環(huán)重新定義set來(lái)清空set
????????????for?(int?j?=?i+1;?j?<?nums.Length;?j++)
????????????{
????????????????if?(j>i+2&&?nums[j]==?nums[j-1]&&?nums[j]==nums[j-2])
????????????????{
????????????????????continue;
//若j重復(fù)則進(jìn)行下一次循環(huán)
????????????????}
????????????????int?c?=?0?-?nums[i]?-?nums[j];
????????????????if?(set.Contains(c))
????????????????{
????????????????????IList<int>?cur?=?new?List<int>();
????????????????????cur.Insert(0,nums[i]);
????????????????????cur.Insert(1,nums[j]);
????????????????????cur.Insert(2,c);
????????????????????result.Add(cur);
????????????????????set.Remove(c);
//排除重復(fù)的c
????????????????}
????????????????else
????????????????{
????????????????????set.Add(nums[j]);
//若沒(méi)找到就將set更新
????????????????}
????????????}
????????}
????????return?result;
????}
}
/*本題比起哈希表更適合用雙指針?lè)?，遍歷一次數(shù)組第0到nums.Length-2位，對(duì)每個(gè)數(shù)用left和right兩個(gè)指針指向它的下一位和最后一位，并根據(jù)三數(shù)相加結(jié)果決定left和right指針向中間移動(dòng)，有結(jié)果則記錄下來(lái)，實(shí)現(xiàn)代碼如下*/
public?class?Solution?{
????
????public?IList<IList<int>>?ThreeSum(int[]?nums)
????{
????????Array.Sort(nums);
????????IList<IList<int>>?rsl?=?new?List<IList<int>>();
????????int?i?=?0,?j?=?0,?k?=?0;
????????for?(?i?=?0;?i?<?nums.Length-2;?i++)
????????{
????????????if?(i>0&&nums[i]==nums[i-1])
????????????{
????????????????continue;
//去重復(fù)
????????????}
????????????j?=?i?+?1;
????????????k?=?nums.Length?-?1;
????????????while?(j<k)
????????????{
????????????????
????????????????if?(nums[k]+nums[j]+nums[i]<0)
????????????????{
????????????????????j?+=?1;
//left指針移動(dòng)
????????????????????while?(j<k&&nums[j]==nums[j-1])
????????????????????{
????????????????????????j?+=?1;
//去重復(fù)
????????????????????}
????????????????}
????????????????else?if?(nums[k]+nums[j]+nums[i]>0)
????????????????{
????????????????????k?-=?1;
//right指針移動(dòng)
????????????????????while?(j<k&&nums[k]==nums[k+1])
????????????????????{
????????????????????????k?-=?1;
//去重復(fù)
????????????????????}
????????????????}
????????????????else
????????????????{
????????????????????List<int>?temp=new?List<int>(3);
????????????????????temp.Add(nums[i]);
????????????????????temp.Add(nums[j]);
????????????????????temp.Add(nums[k]);
????????????????????rsl.Add(temp);
????????????????????j?+=?1;
//找到結(jié)果后未遍歷結(jié)束要繼續(xù)遍歷
????????????????????while?(j<k&&nums[j]==nums[j-1])
????????????????????{
????????????????????????j?+=?1;
????????????????????}
????????????????????k?-=?1;
????????????????????while?(j<k&&nums[k]==nums[k+1])
????????????????????{
????????????????????????k?-=?1;
//找到結(jié)果后也要去重復(fù)
????????????????????}
????????????????}
????????????????
????????????
????????????}
????????}
????????return?rsl;
????}
}
力扣18：四數(shù)之和
//解法與上一道題相同，只是要循環(huán)外多套一次for循環(huán)，然后再用雙指針?lè)ㄕ业椒蠗l件的數(shù)
public?class?Solution?{
???public?IList<IList<int>>?FourSum(int[]?nums,int?target)
????{
????????IList<IList<int>>?result?=?new?List<IList<int>>();
????????
????????Array.Sort(nums);
????????
????????for?(int?i?=?0;?i?<?nums.Length;?i++)
????????{
????????????if?(i>0&&?nums[i]==nums[i-1])?
????????????{
????????????????continue;
????????????}
????????????for?(int?j?=?i+1;?j?<?nums.Length;?j++)
????????????{
????????????????if?(j>i+1&&?nums[j]==nums[j-1])
????????????????{
????????????????????continue;
????????????????}
????????????????int?left?=?j?+?1;
????????????????int?right?=?nums.Length?-?1;
????????????????while?(left<right)
????????????????{
????????????????????long?s?=?(long)nums[i]?+?(long)nums[j]?+?(long)nums[right]?+?(long)nums[left];
//這里由于-10^9<= nums[i] <= 10^9導(dǎo)致進(jìn)行加法計(jì)算時(shí)可能出現(xiàn)數(shù)據(jù)溢出的情況，因此轉(zhuǎn)換成long型進(jìn)行計(jì)算
????????????????????if?(s>target)
????????????????????{
????????????????????????right--;
????????????????????}
????????????????????else?if?(s<target)
????????????????????{
????????????????????????left++;
????????????????????}
????????????????????else
????????????????????{
????????????????????????List<int>?temp=new?List<int>(4);
????????????????????????temp.Add(nums[i]);
????????????????????????temp.Add(nums[j]);
????????????????????????temp.Add(nums[left]);
????????????????????????temp.Add(nums[right]);
????????????????????????result.Add(temp);
????????????????????????while?(right>left&&?nums[right]==nums[right-1])
????????????????????????{
????????????????????????????right--;
????????????????????????}
????????????????????????while?(right>left&&?nums[left]==nums[left+1])
????????????????????????{
????????????????????????????left++;
????????????????????????}
????????????????????????right--;
????????????????????????left++;
????????????????????}
????????????????????
????????????????????}
????????????}
????????}
????????return?result;
????}
}
