目錄

52. 力扣1 兩數之和

52.1 題目解析：

52.2 算法思路：

52.3 代碼演示：

?編輯

52.4 總結反思：

53 面試題：判定是否互為字符重排

53.1 題目解析：

53.2 算法思路：

53.3 代碼演示：

?編輯

53.4 總結反思

54. 力扣217 存在重復元素I

54.1 題目解析：

54.2 算法思路：

54.3 代碼演示：

?編輯

54.4總結反思：

55. 力扣219 存在重復的元素II

55.1 題目解析：

?編輯?

55.2 算法思路：

55.3 代碼演示：

?編輯

55.4 總結反思

56. 力扣49 字母異位詞分組

56.1 題目解析：

?編輯?

56.2 算法思路：

56.3 代碼演示：

?編輯

56.4 總結反思：

?

?

?

?

?

---

今天的算法題是我從暑假寫博客以來最簡單的一次。廢話少說，開啟今天的算法題

在此之前，咱們要先講一下哈希表：

1.哈希表是什么？（哈希表使用方式比較單一），它是存儲數據的容器。

2.那么哈希表有啥用呢？快速查找某個元素，基本接近O（1）級別。

3.什么時候用哈希表？當頻繁的查找某一個數的時候用哈希表，或者使用二分查找，但是二分查找局限性比較大。你用哈希表是因為哈希表比較快，但是呢，能用二分查找還是用二分查找，因為哈希表是典型的用空間換時間。

4.怎么用哈希表？1.容器（哈希表）2.使用數組模擬簡易的哈希表。一般適用于：

【1】字符串中的“字符”，（基本創建一個大小為200的數組空間即可）,<index,n[index]>

? 【2】數據范圍比較小的時候，比如int，1~10^3或4或5,每一個下標對應一個數，但是當出現負數的話，就不建議使用了。

OK，那么關于哈希表的前置知識已經講完了，那么接下來，就正式的進入咱們今天的講題階段

52. 力扣1 兩數之和

52.1 題目解析：

本題很簡單的題目吧。

52.2 算法思路：

那么這個題目，咱們可以使用暴力枚舉來做，不過這個暴力枚舉，并不是非常干脆的暴力枚舉，還是需要一點智慧的。那么下面我就舉個例子，大家看一看。

?

就是固定住一個數字，然后，從這個固定的數字后面去尋找對應的數字即可。那么此時就有兩種尋找方式，一個是從前往后，一個是從后往前

優化：

那么咱們對于這種暴力解法，咱們該如何優化呢？

?

優化就是根據前面的暴力解法來進行的優化，由上面的解析可以看出優化的結果。

52.3 代碼演示：

vector<int> twoSum(vector<int>& nums, int target) {unordered_map<int, int> hash;//<nums[i],i>for (int i = 0; i < nums.size(); i++){int x = target - nums[i];//這個是在哈希表中找到這個數if (hash.count(x)) return { hash[x],i };//這個hash[x]，返回的是x的下標。count，如果哈希表中有這個key，就返回1，否則，返回0hash[nums[i]] = i;//如果沒有這個數字，那么就存儲這個數字，并且存下這個數字的下標，因為上面那行代碼需要用到下標}return { -1,-1 };
}
int main()
{vector<int> nums = { 2,7,11,15 };int target = 9;vector<int> outcome = twoSum(nums, target);for (auto& e : outcome){cout << e << "";}cout << endl;return 0;
}

52.4 總結反思：

本題基本就用到咱們之前所講的那些東西，這里創建哈希表使用unordered_map，是因為這里有key以及val，不只是key

53 面試題：判定是否互為字符重排

53.1 題目解析：

題目也會相當的簡單，而且，咱們上面也說了，只要是關于字符串存儲的，都可以使用到哈希表

53.2 算法思路：

那么本題就是使用哈希表，使用一個，這里有一個細節，就是遍歷s1的字符之后，再遍歷s2。如果在s2找到與s1相同的字符，就減一，如果最后減到負數，則返回false。并且若兩個字符串長度不相等則直接返回false即可。

53.3 代碼演示：

bool CheckPermutation(string s1, string s2) {if (s1.size() != s2.size()) return false;int hash[26] = { 0 };for (auto& e : s1){hash[e - 'a']++;}for (auto& e : s2){hash[e - 'a']--;if (hash[e - 'a'] < 0) return false;}return true;
}
int main()
{string s1("abc");string s2("bca");cout << CheckPermutation(s1, s2) << endl;return 0;
}

53.4 總結反思

基本也是用到了咱們開篇所講的那些知識

54. 力扣217 存在重復元素I

54.1 題目解析：

這題目更不需要多說

54.2 算法思路：

那么咱們這一題主要就是使用哈希表去完成：

這一道題與那個兩數之和的題目策略很像，咱們可以使用那個策略去做，也是使用哈希表，只不過，這一次，只需要有一個key值即可，不需要存val，所以使用unordered_set即可。

54.3 代碼演示：

bool containsDuplicate(vector<int>& nums)
{unordered_set<int> hash;for (auto e : nums){if (hash.count(e)) return true;hash.insert(e);}return false;
}
int main()
{vector<int> nums = { 1,2,3,1 };cout << containsDuplicate(nums) << endl;return false;
}

54.4總結反思：

基本的重要的知識，學會運用，做題輕輕松松

55. 力扣219 存在重復的元素II

55.1 題目解析：

?

這個題目與前面的那一個題目很像，只是多了一個條件而已

55.2 算法思路：

由于這個得使用到下標，所以咱們還是使用unordered_map進行創建哈希表

55.3 代碼演示：

bool containsNearbyDuplicate(vector<int>& nums, int k) {unordered_map<int, int> hash;for (int i = 0; i < nums.size(); i++){if (hash.count(nums[i])){if ((i - hash[nums[i]]) <= k) return true;}hash[nums[i]] = i;}return false;
}
int main()
{vector<int> nums = { 1,2,3,1 };int k=3;cout << containsNearbyDuplicate(nums, k) << endl;return 0;
}

55.4 總結反思

那么大體的思路基本就是這樣，大家還是得利用好前面的知識才可以

56. 力扣49 字母異位詞分組

56.1 題目解析：

?

這個題目很簡單，就是具有相同的字母的字符串就可以合成一組異位詞。

56.2 算法思路：

這個還是得使用哈希表，1.判斷兩個字符是否為字母異位詞，排序

2.然后就是如何分組？<string,string[]>，第二個存的是字符數組。例如，"aet","tea"若字符串中有這個字母，那么加入到字符串數組即可

即val就是咱們所要的結果

56.3 代碼演示：

vector<vector<string>> groupAnagrams(vector<string>& strs)
{unordered_map<string, vector<string>> hash;// 1. 把所有的字?異位詞分組for (auto& s : strs){string tmp = s;sort(tmp.begin(), tmp.end());hash[tmp].push_back(s);}// 2. 結果提取出來vector<vector<string>> ret;for (auto& [x, y] : hash){ret.push_back(y);}return ret;
}
int main()
{vector<string> str = { "eat", "tea", "tan", "ate", "nat", "bat" };vector<vector<string>> outcome = groupAnagrams(str);for (auto& e : outcome){for (auto& x : e){cout << x << "";}cout << endl;}return 0;
}

56.4 總結反思：

基本今天的題目就是這些，算是比較簡單的。

本篇完....................?

?

?

?

?

?