242. 有效的字母異位詞
解題思路：暴力解法就是兩層for循環(huán)，另一種思路就是采用哈希表的方法执隧。
首先定義一個(gè)可以剛好存放所有字母的數(shù)組揩抡，并且每個(gè)元素初始化為0。
接著首先對(duì)第一個(gè)字符串每個(gè)元素進(jìn)行遍歷镀琉，取出每個(gè)字符和a相減峦嗤，相減可以得到當(dāng)前字符在26個(gè)字母中所處的位置，然后將這個(gè)數(shù)字作為索引屋摔，讓記錄結(jié)果的數(shù)組result相應(yīng)位置加上一烁设。上述過程中，字母與result對(duì)應(yīng)位置相互映射钓试，形成了一個(gè)哈希表的結(jié)構(gòu)装黑。
接著遍歷第二個(gè)字符串，同樣通過和a的相減運(yùn)算弓熏，得到了字符串中各個(gè)字符在result的位置映射恋谭，然后在相應(yīng)位置做自減操作。
最終對(duì)結(jié)果數(shù)組進(jìn)行遍歷硝烂，查找是否有不等于0的位置箕别，如果有，說明兩字符串不滿足要求滞谢，返回false串稀。否則為真。
class Solution {
public:
bool isAnagram(string s, string t) {
int record[26] = {0};
for (int i = 0; i < s.size(); i++) {
// 并不需要記住字符a的ASCII狮杨，只要求出一個(gè)相對(duì)數(shù)值就可以了
record[s[i] - 'a']++;
}
for (int i = 0; i < t.size(); i++) {
record[t[i] - 'a']--;
}
for (int i = 0; i < 26; i++) {
if (record[i] != 0) {
// record數(shù)組如果有的元素不為零0母截，說明字符串s和t 一定是誰多了字符或者誰少了字符。
return false;
}
}
// record數(shù)組所有元素都為零0橄教，說明字符串s和t是字母異位詞
return true;
}
};
349. 兩個(gè)數(shù)組的交集
解題思路：
這個(gè)題目也屬于哈希表相關(guān)的題目喘漏，用到的數(shù)據(jù)結(jié)構(gòu)叫做unordered_set，該容器的讀取速率很高负饲，而且不存在重復(fù)數(shù)據(jù)洞坑。當(dāng)數(shù)組的元素?cái)?shù)目很多的時(shí)候瓢剿，使用數(shù)組會(huì)浪費(fèi)較大的內(nèi)存。
首先是用unordered_set的result_set來存放結(jié)果，再新建nums_set用于存放第一個(gè)數(shù)組。
接著遍歷第二個(gè)數(shù)組中的每一個(gè)元素傍睹，通過find函數(shù)在nums_set中找該元素腊脱，找到的話，該函數(shù)會(huì)返回那個(gè)元素的迭代器拂盯，并將該元素放到結(jié)果數(shù)組中。如果不存在就會(huì)返回end()迭代器蜕便。
遍歷完畢之后丛楚，由于結(jié)果都保存在了result中坏平，返回值的類型要求是vector顾瞪，所以將結(jié)果重新放到一個(gè)vector容器中惕橙。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set; // 存放結(jié)果
unordered_set<int> nums_set(nums1.begin(), nums1.end());
for (int num : nums2) {
// 發(fā)現(xiàn)nums2的元素 在nums_set里又出現(xiàn)過
if (nums_set.find(num) != nums_set.end()) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
當(dāng)然本道題尘应，如果對(duì)數(shù)組大小劃定了范圍，那么依然可以采用數(shù)組洒疚，完成哈希表的映射：把數(shù)組的數(shù)值映射到新的哈希數(shù)組的索引。
class Solution {
public:
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set; // 存放結(jié)果吠昭，之所以用set是為了給結(jié)果集去重
int hash[1005] = {0}; // 默認(rèn)數(shù)值為0
for (int num : nums1) { // nums1中出現(xiàn)的字母在hash數(shù)組中做記錄
hash[num] = 1;
}
for (int num : nums2) { // nums2中出現(xiàn)話蘑拯，result記錄
if (hash[num] == 1) {
result_set.insert(num);
}
}
return vector<int>(result_set.begin(), result_set.end());
}
};
202. 快樂數(shù)
解題思路：
當(dāng)需要快速判斷一個(gè)元素是否出現(xiàn)在一個(gè)集合中的時(shí)候，就可以考慮使用哈希法玄窝。
本題目的意思是趣斤，針對(duì)于一個(gè)整形數(shù)势腮，每個(gè)數(shù)位上的數(shù)字求平方和署照，得到一個(gè)新的數(shù)字懂扼，然后繼續(xù)同樣的操作炕倘。
首先定義一個(gè)函數(shù)來完成對(duì)數(shù)字的每個(gè)位上的數(shù)字進(jìn)行平方和操作涨醋。
然后溯警，定義一個(gè)set集合，數(shù)據(jù)類型為unodered_set喳挑。接著定義一個(gè)死循環(huán)伊诵，不斷進(jìn)行求平方和操作，判斷結(jié)果是否等一询张，結(jié)果是一的話份氧，返回true弯屈。如果不為一，判斷這個(gè)數(shù)之前是否出現(xiàn)過厅缺，如果出現(xiàn)過湘捎，說明陷入循環(huán)窄刘，但結(jié)果不為一，返回false活翩。
class Solution {
public:
// 取數(shù)值各個(gè)位上的單數(shù)之和
int getSum(int n) {
int sum = 0;
while (n) {
sum += (n % 10) * (n % 10);
n /= 10;
}
return sum;
}
bool isHappy(int n) {
unordered_set<int> set;
while(1) {
int sum = getSum(n);
if (sum == 1) {
return true;
}
// 如果這個(gè)sum曾經(jīng)出現(xiàn)過材泄，說明已經(jīng)陷入了無限循環(huán)了吨岭，立刻return false
if (set.find(sum) != set.end()) {
return false;
} else {
set.insert(sum);
}
n = sum;
}
}
};
1. 兩數(shù)之和
解題思路：
由于改題目不僅需要確定是否存在簿废，還要返回對(duì)應(yīng)元素的索引络它，所以無法使用數(shù)組或集合，它們都只能映射為索引单料。但是map結(jié)構(gòu)卻可以映射為索引和值的組合。
首先遍歷目標(biāo)數(shù)組中的每個(gè)元素白对，然后找map中是否有有一個(gè)元素换怖，它的值為目標(biāo)值和當(dāng)前元素的差值，也就是另一個(gè)目標(biāo)元素的值条摸。將返回值的迭代器返回給iter钉蒲，用迭代器判斷是否存在該目標(biāo)值是否存在彻坛，如果存在，返回這個(gè)值的迭代器和當(dāng)前元素的索引钙蒙。如果返回的迭代器為end(),說明不存在仪搔，那么就將這個(gè)元素插入到map中蜻牢。
如果直到遍歷結(jié)束抢呆，都找不到這樣的值笛谦，返回一個(gè)空vector。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
std::unordered_map <int,int> map;
for(int i = 0; i < nums.size(); i++) {
// 遍歷當(dāng)前元素恳邀，并在map中尋找是否有匹配的key
auto iter = map.find(target - nums[i]);
if(iter != map.end()) {
return {iter->second, i};
}
// 如果沒找到匹配對(duì)谣沸，就把訪問過的元素和下標(biāo)加入到map中
map.insert(pair<int, int>(nums[i], i));
}
return {};
}
};
