目录
①力扣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 <= 10^4
-10^9 <= nums[i] <= 10^9
-10^9 <= target <= 10^9
- 只会存在一个有效答案
进阶:你可以想出一个时间复杂度小于 O(n2)
的算法吗?
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
}
};
解析代码
事先将数组内的元素和下标绑定在⼀起存入哈希表中,然后直接在哈希表中查找每⼀个元素的 target - nums[i] ,就能快速的找到目标和的下标。
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int, int> hash; // 数组元素和下标
for(int i = 0; i < nums.size(); ++i)
{
auto it = hash.find(target - nums[i]);
if(it != hash.end())
return {it->second, i};
hash[nums[i]] = i;
}
return {-1, -1}; // 照顾编译器
}
};
②力扣面试题 01.02. 判定是否互为字符重排
难度 简单
给定两个由小写字母组成的字符串 s1
和 s2
,请编写一个程序,确定其中一个字符串的字符重新排列后,能否变成另一个字符串。
示例 1:
输入:s1
= "abc",s2
= "bca" 输出: true
示例 2:
输入:s1
= "abc",s2
= "bad" 输出: false
说明:
0 <= len(s1) <= 100
0 <= len(s2) <= 100
class Solution {
public:
bool CheckPermutation(string s1, string s2) {
}
};
解析代码
当两个字符串的长度不相等的时候,是不可能构成互相重排的,直接返回 false。
如果两个字符串能够构成互相重排,那么每个字符串中各个字符出现的次数⼀定是相同的。因此,可以分别统计出这两个字符串中各个字符出现的次数,然后逐个比较是否相等即可。这样的话,就可以选择哈希表来统计字符串中字符出现的次数。
class Solution {
public:
bool CheckPermutation(string s1, string s2) {
if(s1.size() != s2.size())
return false;
int hash[26] = {0};
for(auto& e : s1) // s1元素全部进入哈希表
{
hash[e - 'a']++;
}
for(auto& e : s2) // 判断哈希表中有没有s2元素
{
hash[e - 'a']--;
if(hash[e - 'a'] < 0)
return false;
}
return true;
}
};
③力扣217. 存在重复元素
难度 简单
给你一个整数数组 nums
。如果任一值在数组中出现 至少两次 ,返回 true
;如果数组中每个元素互不相同,返回 false
。
示例 1:
输入:nums = [1,2,3,1] 输出:true
示例 2:
输入:nums = [1,2,3,4] 输出:false
示例 3:
输入:nums = [1,1,1,3,3,4,3,2,4,2] 输出:true
提示:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
}
};
解析代码
至少两次的意思就是数组中存在着重复的元素,因此可以无需统计元素出现的数目。仅需在遍历数组的过程中,检查当前元素是否在之前已经出现过即可。
因此可以利用哈希表,仅需存储数组内的元素。在遍历数组的时候,一边检查哈希表中是否 已经出现过当前元素,一边将元素加入到哈希表中。
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
unordered_set<int> hash;
for(auto& e : nums)
{
if(hash.count(e)) // 如果哈希表中存在此元素
return true;
hash.insert(e);
}
return false;
}
};
④力扣219. 存在重复元素 II
难度 简单
给你一个整数数组 nums
和一个整数 k
,判断数组中是否存在两个 不同的索引 i
和 j
,满足 nums[i] == nums[j]
且 abs(i - j) <= k
。如果存在,返回 true
;否则,返回 false
。
示例 1:
输入:nums = [1,2,3,1], k = 3 输出:true
示例 2:
输入:nums = [1,0,1,1], k = 1 输出:true
示例 3:
输入:nums = [1,2,3,1,2,3], k = 2 输出:false
提示:
1 <= nums.length <= 10^5
-10^9 <= nums[i] <= 10^9
0 <= k <= 10^5
class Solution {
public:
bool containsNearbyDuplicate(vector<int>& nums, int k) {
}
};
解析代码
快速定位到两个信息: 两个相同的元素, 这两个相同元素的下标。 因此,可以使用哈希表,令数组内的元素做 key 值,该元素所对应的下标做 val 值,将数组元素和下标绑定在⼀起,存到哈希表中。
class Solution {
public:
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(hash[nums[i]] - i <= k) // 如果此元素下标与当前下标的差<=k
return true;
}
hash[nums[i]] = i; // 覆盖前面的也没事,因为找<=k的
}
return false;
}
};
⑤力扣49. 字母异位词分组
难度 中等
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的所有字母得到的一个新单词。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
提示:
1 <= strs.length <= 10^4
0 <= strs[i].length <= 100
strs[i]
仅包含小写字母
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
}
};
解析代码
互为字母异位词的单词有⼀个特点:将它们排序之后,两个单词应该是完全相同的。 所以可以利用这个特性,将单词按照字典序排序,如果排序后的单词相同的话,就划分到同一组中。
这时我们就要处理两个问题:
- 排序后的单词与原单词需要能互相映射
- 将排序后相同的单词划分到同⼀组
利用语言提供的容器的强大的功能就能实现这两点:
- 将排序后的字符串( string )当做哈希表的 key 值
- 将字母异位词数组( vector<string> )当成 val 值。
class Solution {
public:
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> hash;
for(auto& e : strs)
{
string tmp = e;
sort(tmp.begin(), tmp.end()); // 排序后异位次的key值都相等了
hash[tmp].push_back(e);
}
vector<vector<string>> ret;
for(auto& [x, y] : hash) // 范围for得到两个值的用法
{
ret.push_back(y);
}
return ret;
}
};
本篇完。
下一篇是简单多问题dp类型的动态规划,下下篇是字符串类型的OJ。
标签:hash,14,nums,Offer,由易到难,元素,示例,vector,哈希 From: https://blog.csdn.net/GRrtx/article/details/136544025