📒博客首页:热爱编程的大李子 📒
🌞文章目的:Hash表算法题整理分享🌞
🙏博主在学习阶段,如若发现问题,请告知,非常感谢🙏
💙同时也非常感谢各位小伙伴们的支持💙
🌈每日一语:承遇朝霞,年少正恰。整装戎马,刻印风华! 🌈
💗感谢: 我只是站在巨人们的肩膀上整理本篇文章,感谢走在前路的大佬们!💗
🌟最后,祝大家每天进步亿点点! 欢迎大家点赞👍➕收藏⭐️➕评论💬支持博主🤞!🌟
⭐️ ⭐️上篇文章-<代码随想录二刷>链表 ⭐️ ⭐️
文章目录- 242. 有效的字母异位词
- 题目描述
- 思路分析
- 参考代码
- 49. 字母异位词分组
- 题目描述
- 思路分析
- 参考代码
- 438. 找到字符串中所有字母异位词
- 题目描述
- 思路分析
- 参考代码
- 383. 赎金信
- 题目描述
- 思路分析
- 参考代码
- 349. 两个数组的交集
- 题目描述
- 思路分析
- 参考代码
- 350. 两个数组的交集 II
- 题目分析
- 思路分析
- 参考代码
- 202. 快乐数
- 题目描述
- 思路分析:
- 参考代码
- 1. 两数之和
- 题目描述
- 思路分析
- 参考代码
- 15. 三数之和
- 题目描述
- 思路分析
- 参考代码
- 18. 四数之和
- 题目描述
- 思路分析
- 参考代码
- 454. 四数相加 II
- 题目描述
- 思路分析
- 参考代码
- 总结
242. 有效的字母异位词 题目描述
给定两个字符串 s 和 t ,编写一个函数来判断 t 是否是 s 的字母异位词。
注意:若 s 和 t 中每个字符出现的次数都相同,则称 s 和 t 互为字母异位词。
示例 1:
输入: s = "anagram", t = "nagaram"
输出: true
示例 2:
输入: s = "rat", t = "car"
输出: false
思路分析
方法一:hash表
由于字符串中的都是小写字母,所以我们可以用数组来作为Hash表.
-
将s中的字母出现的种类个数保存到数组arr中.
-
将数组arr减掉t中字母出现的种类个数
-
判断数组arr是否都为0,如果都为0,则说明 s和t是字母异位词.
方法二
直接sort排序,然后判断两个字符串是否相等.
参考代码#include
using namespace std;
//Hash表的使用
bool isAnagram(string s, string t) {
int arr[30] = {0};
for(char ch : s){//统计s中的字母以及个数
arr[ch-'a']++;
}
for(char ch : t) {//用t中的字母和s中的进行抵消..
arr[ch-'a']--;
}
for(int i = 0;i < 30;i++) {
if(arr[i]!=0){
return false;//s和t中有字符不一样.
}
}
return true;
}
- 时间复杂度:O(n)
- 空间复杂度:O(1)
给你一个字符串数组,请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。
字母异位词 是由重新排列源单词的字母得到的一个新单词,所有源单词中的字母都恰好只用一次。
示例 1:
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]
示例 2:
输入: strs = [""]
输出: [[""]]
示例 3:
输入: strs = ["a"]
输出: [["a"]]
思路分析
字母异位词其实就是两个串所使用的的字母以及个数都相同,只是顺序不同.所以如果两个串是字母异位词,则这两个串排序后是相等的.
- 我们可以使用map来存储解决,因为不要求有序和可重复性,所以我们可以使用 unordered_map
- 我们依次对字符串数组进行遍历,如果当前字符串排序后在map中出现过,则将其存入该key对应的val数组中.如果没有出现过则创建以该串为键的键值对.
- 最终遍历Map将结果存放到vector数组中.
#include
using namespace std;
vector<vector<string>> groupAnagrams(vector<string>& strs) {
unordered_map<string,vector<string>> M;
vector<vector<string>> res;
string s;
for(int i = 0; i < strs.size(); i++) { //
s = strs[i];
sort(s.begin(),s.end());
M[s].push_back(strs[i]);
}
//遍历输出
for(unordered_map<string,vector<string>>::iterator it = M.begin(); it!=M.end(); it++) {
res.push_back(it->second);
}
return res;
}
438. 找到字符串中所有字母异位词 题目描述
给定两个字符串 s 和 p,找到 s 中所有 p 的 异位词 的子串,返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串(包括相同的字符串)。
示例 1:
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
示例 2:
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的异位词。
方法一:滑动窗口法+hash表
由于字符串中的都是小写字母,所以我们可以用数组的下标进行映射.即选择数组类型的hash表; 由于求的是子串的异位词,可以使用一个滑动窗口法:窗口大小固定,从前往后移动,寻找符合的子串.
- 初始化滑动窗口.也就是对arrS和arrP初始化. arrS中至少含有arrP中的所有元素.
- 判断初始化后的窗口是否相等,如果相同则将其实下标0加入结果集.
- S滑动窗口向后移动寻找满足的子串满足是P的异位词,并将满足的起始下标加入结果集.
- 返回结果集
bool judgeArr(int arr1[],int arr2[]) { //判断两个数组是否相等
for(int i = 0; i < 30; i++) {
if(arr1[i]!=arr2[i]) {
return false;
}
}
return true;
}
//滑动窗口法+hash表
vector<int> findAnagrams(string s, string p) {
int m = s.size();
int n = p.size();
vector<int> res;
int arrS[30] = {0};
int arrP[30] = {0};
if(s.size() <p.size()) {//长度s < p,则s中不可能存在子串 和p是异位词
return {};
}
//初始化滑动窗口 s的窗口至少含有p中的所有元素
for(int i = 0; i < n; i++) {
arrS[s[i]-'a']++;
arrP[p[i]-'a']++;
}
if(judgeArr(arrS,arrP)) {//判断初始化后的窗口是否相等
res.push_back(0);
}
//s滑动窗口移动寻找子串满足是p的异位词 注意:s的窗口大小和p相等
for(int i = n; i<m; i++) {
arrS[s[i]-'a']++;
arrS[s[i-n]-'a']--;
if(judgeArr(arrS,arrP)) {
res.push_back(i-n+1);
}
}
return res;
}
383. 赎金信
题目描述
为了不在赎金信中暴露字迹,从杂志上搜索各个需要的字母,组成单词来表达意思。
给你一个赎金信 (ransomNote) 字符串和一个杂志(magazine)字符串,判断 ransomNote 能不能由 magazines 里面的字符构成。
如果可以构成,返回 true ;否则返回 false 。
magazine 中的每个字符只能在 ransomNote 中使用一次。
示例 1:
输入:ransomNote = "a", magazine = "b"
输出:false
示例 2:
输入:ransomNote = "aa", magazine = "ab"
输出:false
示例 3:
输入:ransomNote = "aa", magazine = "aab"
输出:true
思路分析
方法一:hash表
因为是字符,所以可以采用数组的hash表(也可以使用unordered_map的hash表,因为考虑到效率而且还不需要排序)
**注:**使用数组还是使用set/map类型的hash表,要认真考虑.如果元素用数组可以很好的表示并且范围很小,那就考虑数组.比如元素字符… 本题使用数组较为简单
方法二:双指针
- 先对两个串排序.
- i指向ransomNote串,j指向magazine串.然后从前往后遍历俩串,如果相同就都++,如果j对应的字符大于了i对应的字符,说明不满足了. 如果j对应的字符小于i对应的字符,说明magazine中的该字符是满足的而且还多余.
- 如果i能遍历完ransomNote,则说明能找到符合题意的串.
方法一:hash表(数组)
//直接LeetCode242进行改造... 数组做hash表
bool canConstruct(string s, string t) {
int arr[30] = {0};
for(char ch : s){//统计s中的字母以及个数
arr[ch-'a']++;
}
for(char ch : t) {//用t中的字母和s中的进行抵消..
arr[ch-'a']--;
}
for(int i = 0;i < 30;i++) {
if(arr[i]>0){
return false;//s和t中有字符不一样.
}
}
return true;
}
//使用map作为哈希表
bool canConstruct(string s1, string s2) {
if(s1.size()>s2.size()) {
return false;
}
unordered_map<char,int> sMap;
for(char c : s2) {
if(sMap.find(c)==sMap.end()) {
sMap[c] = 1;
} else {
sMap[c]++;
}
}
for(char c : s1) {
if(sMap.find(c)!=sMap.end()) {
sMap[c]--;
if(sMap[c]<0){
return false;
}
}else{
return false;
}
}
return true;
}
-
时间复杂度 O(n)
-
空间复杂度O(n)
方法二:双指针
bool canConstruct(string ransomNote, string magazine) {
if(ransomNote.size()>magazine.size()) {
return false;
}
sort(ransomNote.begin(),ransomNote.end());
sort(magazine.begin(),magazine.end());
//cout<
int i,j;
for(i = 0,j = 0; i < ransomNote.size(); i++,j++) {
if(j>=magazine.size()) {
return false;
}
if(ransomNote[i]==magazine[j]) {
continue;
} else if(ransomNote[i]>magazine[j]) {
i--;
} else {
return false;
}
}
return true;
}
349. 两个数组的交集
题目描述
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[9,4]
思路分析
方法一:hash表
- 由样例可知,最后的结果是要去重的. 我们选择unordered_set类型的hash表:输出结果中的每个元素一定是唯一的, 同时可以不考虑输出结果的顺序
**注:**由于数组中数的返回比较大,所以不建议使用数组来作为hash表.
方法二:暴力法(此法代码省略)
-
先给nums1和nums2排序.
-
然后双层循环判断nums1的元素是否出现在了nums2中.
-
判断过程中要进行去重:nums1中循环的元素和前一个相等则不处理,不相等再去nums2中判断是否存在
-
将nums1和nums2都存在的元素加入结果集
方法一:hash表
#include
using namespace std;
//方法一: 先给nums1和nums2排序.然后双层循环判断nums1的元素是否出现在了nums2中.遍历时,如果元素和前一个相等则不处理,不相等再去nums2中判断是否存在.
//方法二:先去重使用nums1_set 然后遍历nums2,判断元素在nums1_set中是否出现,如果出现则加入结果集合..O(N) unordered_set的查找效率是O(1)
//另外通过这个题,也要学到vector初始化set,set初始化vector的知识点
vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
unordered_set<int> result_set;//结果集
unordered_set<int> nums1_set(nums1.begin(),nums1.end()) ;
for(int i = 0; i < nums2.size(); i++) {
//如果发现 nums2的元素 ,在nums1_set中出现过
if(nums1_set.find(nums2[i])!=nums1_set.end()) {
result_set.insert(nums2[i]) ;
}
}
return vector<int>(result_set.begin(),result_set.end());
}
350. 两个数组的交集 II
题目分析
给定两个数组,编写一个函数来计算它们的交集。
示例 1:
输入:nums1 = [1,2,2,1], nums2 = [2,2]
输出:[2,2]
示例 2:
输入:nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出:[4,9]
思路分析
方法一:hash表
因为不去重,不考虑顺序,而且考虑到了效率我们可以采用unordered_map类型的hash表
- 把nums1中的元素放到
unordered_map
中,然后遍历nums2中的每个元素num.nums1_map - 如果num在numsMap的值>0,则说明可以放到交集里面…如果等于0,则从numsMap中移除.
方法二:双指针
思路与LeetCode384相似,不再赘述
参考代码方法一:hash表
//方法一:使用unordered_map解决. 原因:因为同一个数存在多个,可以使用键值对来进行存储,结果不要求顺序.
//时间复杂度O(N) 空间复杂度O(N)
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
unordered_map<int,int> nums1_map;
for(int i = 0; i < nums1.size(); i++) { //初始化nums1_map
nums1_map[nums1[i]]++;
}
//遍历nums2,将重复的元素加入结果集.
for(int i = 0; i < nums2.size(); i++) {
if(nums1_map.find(nums2[i])!=nums1_map.end()) {
nums1_map[nums2[i]]--;
result.push_back(nums2[i]);//元素放入结果集
if(nums1_map[nums2[i]]==0) { //如果已经减到了0,则移除
nums1_map.erase(nums2[i]);
}
}
}
return result;
}
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
方法二:双指针
//方法二: 双指针
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
int i = 0,j = 0;
vector<int> result;
//排序
sort(nums1.begin(),nums1.end());
sort(nums2.begin(),nums2.end());
while(i<nums1.size()&&j<nums2.size()){
if(nums1[i]==nums2[j]){//如果想等
result.push_back(nums1[i]);//加入结果集
i++;//同时移动
j++;
}else if(nums1[i]<nums2[j]){//值小的指针往前移动
i++;
}else if(nums1[i]>nums2[j]){
j++;
}
}
return result;
}
202. 快乐数
题目描述
编写一个算法来判断一个数 n 是不是快乐数。
「快乐数」定义为:
对于一个正整数,每一次将该数替换为它每个位置上的数字的平方和。
然后重复这个过程直到这个数变为 1,也可能是 无限循环 但始终变不到 1。
如果 可以变为 1,那么这个数就是快乐数。
如果 n 是快乐数就返回 true ;不是,则返回 false 。
示例 1:
输入:n = 19
输出:true
解释:
12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1
示例 2:
输入:n = 2
输出:false
思路分析:
注意: 题目中的可能会无限循环,也就是说在求和的过程中,sum会重复出现.
- 所以我们就可以对该数进行快乐的判断,每次如果不是1,说明该数目前不是快乐数.
- 同时要在set中寻找该数是否曾经出现过,如果出现过则说明出现了循环则一定不是快乐数.
- 如果还没有出现则持续进行判断…
#include
using namespace std;
int getSum(int x){//将数替换成数字的平方和
int sum = 0;
while(x){
sum+=(x%10)*(x%10);
x /= 10;
}
return sum;
}
//由于只需要存这个元素在集合中是否存在,而且不需要重复,所以我们使用unordered_set
unordered_set<int> set;
bool isHappy(int n) {
int res = getSum(n);
while(res!=1){
if(set.find(res)!=set.end()){
return false;
}else{
set.insert(res);
}
res = getSum(res);
}
return true;
}
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]
思路分析
方法一:暴力法
双层for循环走起来 ~ ~ ~
方法二:hash表(unordered_map)
-
因为每次不仅要存数,还要存储其下标,所以我们使用map,因为不需要有序和重复性,我们可以选择:
unordered_map M
-
用i遍历所有的元素,在M中查找是否存在元素 target - nums[i],如果存在则说明找到了,返回当前元素和这个元素的下标.
-
如果没有找到则将当前元素和下标插入到M中.
方法一:暴力法
//方法一:暴力法
vector<int> twoSum(vector<int>& nums, int target) {
for(int i = 0;i < nums.size();i++) {
for(int j = i+1;j < nums.size();j++){
return {i,j};
}
}
return {};
}
- 时间复杂度: O ( n 2 ) O(n^2) O(n2)
- 空间复杂度: O ( 1 ) O(1) O(1)
方法二:hash表
vector<int> twoSum(vector<int>& nums, int target) {
unordered_map<int,int> M;//存放元素以及对应的下标
for(int i = 0; i < nums.size(); i++) {
unordered_map<int,int>::iterator iter = M.find(target-nums[i]);//查找其和为target的另外 一个元素是否存在
if(iter!=M.end()) {
return {i,iter->second};
}
M.insert(pair<int,int>(nums[i],i));//如果没有,则将当前元素插进来.
}
return {};//写这个只是为了编译通过,实际运行根本不会走这一步..
}
- 时间复杂度: O ( n ) O(n) O(n)
- 空间复杂度: O ( n ) O(n) O(n)
15. 三数之和 题目描述
给你一个包含 n 个整数的数组 nums,判断 nums 中是否存在三个元素 a,b,c ,使得 a + b + c = 0 ?请你找出所有和为 0 且不重复的三元组。
注意:答案中不可以包含重复的三元组。
示例 1:
输入:nums = [-1,0,1,2,-1,-4]
输出:[[-1,-1,2],[-1,0,1]]
示例 2:
输入:nums = []
输出:[]
示例 3:
输入:nums = [0]
输出:[]
思路分析
排序 + 双指针
(1). 特判,对于数组长度 n,如果数组长度小于 3,返回 []。
(2). 对数组进行排序。
(3).遍历排序后数组:
-
若 nums[i]>0:因为已经排序好,所以后面不可能有三个数加和等于 0,直接返回结果。
-
对nums[i] (代表的就是a)进行去重.
-
令左指针 L=i+1,右指针 R=n-1,当 L
(4) 当 nums[i]+nums[L]+nums[R]==0执行循环,判断左界和右界是否和下一位置重复,去除重复解。并同时将 L,R 移到下一位置,寻找新的解
(5).若和大于 0,说明nums[R] 太大,R左移
(6).若和小于 0,说明 nums[L] 太小,L右移
复杂度分析
- 时间复杂度:
O
(
n
2
)
O(n^2)
O(n2)
数组排序 O(n logn),遍历数组O(n),双指针遍历 O(n),总体 O(n logn)+O(n)∗O(n), - 空间复杂度: O ( 1 ) O(1) O(1)
#include
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
int L,R,sum;
vector<vector<int>> res;
if(nums.size()<3) {
return {} ;
}
//进行排序
sort(nums.begin(),nums.end()) ;
//如果第一个元素就>0,那么后面的元素一定 > 0
if(nums[0]>0) {
return {};
}
//遍历元素+双指针
for(int i = 0; i<nums.size(); i++) {
if(nums[i]>0) {
return res;
}
if(i>0&&nums[i]==nums[i-1]) { //进行去重
continue;
}
L = i+1;
R = nums.size()-1;
while(L < R) {//采用双指针法 枚举所有的三元对情况
sum = nums[i]+nums[L]+nums[R];
if(!sum) {
res.push_back({nums[i],nums[L],nums[R]});
//进行去重
while(L + 1<R && nums[L]==nums[L+1]) {
L++;
}
while(R-1 > L && nums[R]==nums[R-1]) {
R--;
}
L++;
R--;
} else if(sum > 0) {
R--;
} else if(sum < 0) {
L++;
}
}
}
return res;
}
18. 四数之和 题目描述
给你一个由 n 个整数组成的数组 nums ,和一个目标值 target 。请你找出并返回满足下述全部条件且不重复的四元组 [nums[a], nums[b], nums[c], nums[d]] (若两个四元组元素一一对应,则认为两个四元组重复):
0 <= a, b, c, d < n
a、b、c 和 d 互不相同
nums[a] + nums[b] + nums[c] + nums[d] == target
你可以按 任意顺序 返回答案 。
示例 1:
输入:nums = [1,0,-1,0,-2,2], target = 0
输出:[[-2,-1,1,2],[-2,0,0,2],[-1,0,0,1]]
示例 2:
输入:nums = [2,2,2,2,2], target = 8
输出:[[2,2,2,2]]
思路分析
和三数之和解决思路基本一致.三数之和只是 i 固定,左右指针进行变化.
四数之和是i,j固定,然后左右指针进行变化,当左右指针变化一轮后,j进行后移一位.j移动完一轮后,i后移一位…
#include
using namespace std;
//这个题思路和上一个题非常相似
vector<vector<int>> fourSum(vector<int>& nums, int target) {
vector<vector<int>> res;
int len = nums.size();
long long i,j,k,l, sum;
if(nums.size()<4) {
return {};
}
//进行排序
sort(nums.begin(),nums.end()) ;
// if(nums[0]>target){//这里不能根据第一个数来判断最终结果,因为target可能是正数,负数,0
// return {};
// }
//定义两个变量+双指针 枚举所有的情况
for(i = 0; i <= len-4; i++) {
//去重i元素
if(i > 0 && nums[i]==nums[i-1]) {//去重
continue;
}
for( j = i+1; j <= len - 3; j++) {
//去重
if(j > i+1 && nums[j] == nums[j-1]) {
continue;
}
//定义双指针
int k = j+1;
int l = len - 1;
while(k < l) {
sum = 0;
sum += nums[i];
sum += nums[j];
sum += nums[k];
sum += nums[l];
if(sum==target) {
res.push_back({nums[i],nums[j],nums[k],nums[l]});
//进行去重
while(k+1 < l &&nums[k] == nums[k+1] ) {
k++;
}
while(l-1>k&& nums[l]==nums[l-1]) {
l--;
}
//指针移动
k++;
l--;
} else if(sum < target) {
k++;
} else if(sum > target) {
l--;
}
}
}
}
return res;
}
454. 四数相加 II 题目描述
给你四个整数数组 nums1、nums2、nums3 和 nums4 ,数组长度都是 n ,请你计算有多少个元组 (i, j, k, l) 能满足:
0 <= i, j, k, l < n
nums1[i] + nums2[j] + nums3[k] + nums4[l] == 0
示例 1:
输入:nums1 = [1,2], nums2 = [-2,-1], nums3 = [-1,2], nums4 = [0,2]
输出:2
解释:
两个元组如下:
- (0, 0, 0, 1) -> nums1[0] + nums2[0] + nums3[0] + nums4[1] = 1 + (-2) + (-1) + 2 = 0
- (1, 1, 0, 0) -> nums1[1] + nums2[1] + nums3[0] + nums4[0] = 2 + (-1) + (-1) + 0 = 0
示例 2:
输入:nums1 = [0], nums2 = [0], nums3 = [0], nums4 = [0]
输出:1
思路分析
由于a,b,c,d是在四个数组里面的,所以可以使用四个循环. 为了降低时间复杂度,我们可以将a、b分为一组,c、d分为一组. 利用map类型的hash表统计其出现的次数.
- 首先定义 一个
unordered_map
,key放a和b两数之和,value 放a和b两数之和出现的次数。 - 遍历大A和大B数组,统计两个数组元素之和,和出现的次数,放到map中。
- 在遍历大C和大D数组,如果 0-(c+d) 在map中出现过的话,统计其出现的次数.
- 最后返回统计值 cnt
#include
using namespace std;
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
unordered_map<int,int> M;
int cnt = 0;
for(int A : nums1){
for(int B : nums2){
M[A+B]++;
}
}
for(int C: nums3){
for(int D: nums4){
auto iter = M.find(0-A-B);
if(M.find(0-A-B)!=M.end()) {
cnt+=iter->second;
}
}
}
return cnt;
}
总结
OK,今天关于hash表算法整理就到这里的,希望本篇文章能够帮助到大家,同时也希望大家看后能学有所获!!!
好了,我们下期见~
欢迎分享,转载请注明来源:内存溢出
评论列表(0条)