算法刷題-哈希表

242. 有效的字母異位詞

給定兩個字符串 *s* 和 *t* ，編寫一個函數(shù)來判斷 *t* 是否是 *s* 的字母異位詞。

**注意：**若 *s* 和 *t* 中每個字符出現(xiàn)的次數(shù)都相同，則稱 *s* 和 *t* 互為字母異位詞。

思路

用一個哈希表來記錄第一個字符串每個字符出現(xiàn)的次數(shù)，然后遍歷第二個字符串，減去他的字母出現(xiàn)的次數(shù)，

最后如果哈希表每個值都是0，說明符合題意

代碼

    bool isAnagram(string s, string t) {map<char,int> m;for(char c:s) m[c]++;for(char c:t) m[c]--;for(auto [x,y]:m) {if(y!=0) return false;}return true;}

349. 兩個數(shù)組的交集

給定兩個數(shù)組 nums1 和 nums2 ，返回 它們的交集 。輸出結(jié)果中的每個元素一定是 唯一 的。我們可以 不考慮輸出結(jié)果的順序 。

思路

用一個set記錄第一個數(shù)組出現(xiàn)了哪些元素，然后再開一個set記錄兩個數(shù)組都出現(xiàn)的元素即可

代碼

    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {vector<int> res;set<int> s,s2;for(int x:nums1) s.insert(x);for(int x:nums2){if(s.count(x)) s2.insert(x);} for(int x:s2) res.push_back(x);return res;}

202. 快樂數(shù)

編寫一個算法來判斷一個數(shù) n 是不是快樂數(shù)。

「快樂數(shù)」 定義為：

• 對于一個正整數(shù)，每一次將該數(shù)替換為它每個位置上的數(shù)字的平方和。
• 然后重復這個過程直到這個數(shù)變?yōu)?1，也可能是 無限循環(huán) 但始終變不到 1。
• 如果這個過程 結(jié)果為 1，那么這個數(shù)就是快樂數(shù)。

如果 n 是 快樂數(shù) 就返回 true ；不是，則返回 false 。

思路

寫一個函數(shù)f來計算每次變化后的結(jié)果

用一個哈希表來存n能變到哪些數(shù)字，如果第二次變到哈希表里的數(shù)字，說明有循環(huán)，退出即可

代碼

    int f(int n){int x=0;while(n) x+=(n%10)*(n%10),n/=10;return x;}bool isHappy(int n) {set<int> s;while(1){if(n==1) return 1;if(s.count(n)) return 0;s.insert(n);n=f(n);}}

1. 兩數(shù)之和

給定一個整數(shù)數(shù)組 nums 和一個整數(shù)目標值 target，請你在該數(shù)組中找出 和為目標值 target 的那 兩個 整數(shù)，并返回它們的數(shù)組下標。

你可以假設(shè)每種輸入只會對應(yīng)一個答案。但是，數(shù)組中同一個元素在答案里不能重復出現(xiàn)。

你可以按任意順序返回答案。

思路

用一個哈希表記錄每個數(shù)字出現(xiàn)的位置

再遍歷一次數(shù)組，如果nums[i]-target在哈希表中存在，說明找到了，直接返回

代碼

    vector<int> twoSum(vector<int>& nums, int target) {map<int,int> m;int n=nums.size();for(int i=0;i<n;i++) m[nums[i]]=i;for(int i=0;i<n;i++){int j=m[target-nums[i]];if(j!=0&&j!=i) return {i,j};}return {0,0};}

454. 四數(shù)相加 II

給你四個整數(shù)數(shù)組 nums1、nums2、nums3 和 nums4 ，數(shù)組長度都是 n ，請你計算有多少個元組 (i, j, k, l) 能滿足：

• 0 <= i, j, k, l < n
• nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0

思路

先將nums1和nums2所有可能得到的值的組合存到哈希表中

在遍歷nums3和nums4，判斷0-nums3[i]-nums4[j]在不在哈希表中

時間復雜度為$O(n^2)$

代碼

    int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {map<int,int> m;for(int x:nums1)for(int y:nums2)m[x+y]++;int res=0;for(int x:nums3)for(int y:nums4)if(m[0-x-y]!=0)res+=m[0-x-y];return res;}

383. 贖金信

給你兩個字符串：ransomNote 和 magazine ，判斷 ransomNote 能不能由 magazine 里面的字符構(gòu)成。

如果可以，返回 true ；否則返回 false 。

magazine 中的每個字符只能在 ransomNote 中使用一次。

思路

將第二個字符串的每個字符出現(xiàn)的次數(shù)存入到哈希表中

在遍歷第一個字符串，對應(yīng)出現(xiàn)的次數(shù)減去

最后判斷是否有出現(xiàn)次數(shù)<0的字母，說明不符合題意

代碼

    bool canConstruct(string ransomNote, string magazine) {map<char,int> m;for(char c:magazine) m[c]++;for(char c:ransomNote) m[c]--;for(auto [x,y]:m) if(y<0) return false;return true;}

15. 三數(shù)之和

給你一個整數(shù)數(shù)組 nums ，判斷是否存在三元組 [nums[i], nums[j], nums[k]] 滿足 i != j、i != k 且 j != k ，同時還滿足 nums[i] + nums[j] + nums[k] == 0 。請

你返回所有和為 0 且不重復的三元組。

**注意：**答案中不可以包含重復的三元組。

思路

先對數(shù)據(jù)進行排序，然后遍歷一次數(shù)組，雙指針不斷縮小范圍

代碼

    vector<vector<int>> threeSum(vector<int>& nums) {sort(nums.begin(),nums.end());vector<vector<int>> res;int n=nums.size();for(int k=0;k<n-2;k++){if(nums[k]>0) break;if(k>0&&nums[k]==nums[k-1]) continue;int i=k+1,j=n-1;while(i<j){int sum=nums[k]+nums[i]+nums[j];if(sum<0)while(i<j &&nums[i]==nums[++i]);else if(sum>0) while(i<j && nums[j]== nums[--j]);else{res.push_back({nums[i],nums[j],nums[k]});while(i<j&&nums[i]==nums[++i]);while(i<j&&nums[j]==nums[--j]);}}}return res;}

18. 四數(shù)之和

給你一個由 n 個整數(shù)組成的數(shù)組 nums ，和一個目標值 target 。請你找出并返回滿足下述全部條件且不重復的四元組 [nums[a], nums[b], nums[c], nums[d]] （若兩個四元組元素一一對應(yīng)，則認為兩個四元組重復）：

• 0 <= a, b, c, d < n
• a、b、c 和 d 互不相同
• nums[a] + nums[b] + nums[c] + nums[d] == target

你可以按 任意順序 返回答案 。

思路

和三數(shù)之和一樣，雙指針算法。

代碼

    vector<vector<int>> fourSum(vector<int>& nums, int target) {sort(nums.begin(),nums.end());vector<vector<int>> res;int n=nums.size();for(int k=0;k<n;k++){if(nums[k]>target&&nums[k]>=0) break;if(k>0 &&nums[k]==nums[k-1] ) continue;for(int i=k+1;i<n;i++){if(i>k+1 &&nums[i]==nums[i-1]) continue;int l=i+1,r=n-1;while(l<r){long long sum=(long long)nums[k]+nums[i]+nums[l]+nums[r];if(sum>target) r--;else if(sum<target) l++;else {res.push_back({nums[k],nums[i],nums[l],nums[r]});while(l<r && nums[l]==nums[l+1])l++;while(l<r &&nums[r]==nums[r-1]) r--;r--,l++;}}}}return res;}