文章目录
- 🤔0.哈希表
- 🌼1. 两数之和
- 🌻1. 题目
- 🌷2. 算法原理
- 🌺3. 代码实现
- 🍈面试题 01.02. 判定是否互为字符重排
- 🍌1. 题目
- 🍏2. 算法原理
- 🍓3. 代码实现
🤔0.哈希表
哈希表用于“快速”查找某个元素，在刷题的时候，如果数据范围不大，我们可以用数组来模拟一个建议的哈希表，C++里面的哈希表是unordered_map，关于哈希表的内容可以查看此篇文章：哈希(hash)——【C++实现】
🌼1. 两数之和
🌻1. 题目
题目链接：1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
示例 2：
输入：nums = [3,2,4], target = 6
输出：[1,2]
示例 3：
输入：nums = [3,3], target = 6
输出：[0,1]
提示：
2 <= nums.length <= 104-109 <= nums[i] <= 109-109 <= target <= 109- 只会存在一个有效答案
**进阶：**你可以想出一个时间复杂度小于 O(n2) 的算法吗？
🌷2. 算法原理
解法一：暴力枚举
这里固定一个元素，然后遍历后面的元素，看看有没有和为target的，两层for循环，时间复杂度为O(N2)
解法二：哈希表
我们找个一个元素之后，只需要看数组里面是否有target-nums[i]的值，要快速确定一个值，采用哈希表。
这里因为要返回元素的下标，所以我们哈希表里面的映射为<nums[i], i>。
不要一次性将元素全部丢进哈希表，例如
target = 4，数组为[2,3,4,5]，如果先全部丢进去，那么到2的时候，哈希表里面有hash[nums[i]] == target - nums[i]的，但是这个情况明显不符合
🌺3. 代码实现
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target)
{
unordered_map<int, int> hash;
for(int i = 0; i < nums.size(); i++)
{
int x = target - nums[i];
if(hash.count(x)) return {i,hash[x]};
hash[nums[i]] = i;
}
return {-1,-1};
}
};
运行结果：
🍈面试题 01.02. 判定是否互为字符重排
🍌1. 题目
题目链接：面试题 01.02. 判定是否互为字符重排
给定两个由小写字母组成的字符串 s1 和 s2，请编写一个程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。
示例 1：
输入: s1 = "abc", s2 = "bca"
输出: true
示例 2：
输入: s1 = "abc", s2 = "bad"
输出: false
说明：
0 <= len(s1) <= 1000 <= len(s2) <= 100
🍏2. 算法原理
解法一：排序+比较
这里可以直接用sort将这2个字符串排序，然后直接比较这两个字符串是否相等即可，排序sort的时间复杂度为O(2N*logN)
解法一：哈希表
这里也能直接统计字符出现的个数，如果这两个字符串字符都相同且出现的个数一样，即代表互为重排列。
这里要创建1个哈希表，但是只有26个英文字母，所以直接用数组模拟哈希表即可。
时间复杂度为O(2N)
🍓3. 代码实现
排序+比较
class Solution {
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size() != s2.size()) return false;
sort(s1.begin(),s1.end());
sort(s2.begin(),s2.end());
return s1 == s2;
}
};
哈希表：
class Solution {
public:
bool CheckPermutation(string s1, string s2)
{
if(s1.size() != s2.size()) return false;
int hash[26] = { 0 };
for(auto ch1 : s1)
hash[ch1 - 'a']++;
for(auto ch2 : s2)
{
hash[ch2 - 'a']--;
if(hash[ch2- 'a'] < 0) return false;
}
return true;
}
};
运行结果：
