哈希表可以同时保存关键字以及关键字的另一个信息，可以是value用于记录数量，也可以是position用于查找地址，当需要同时考虑关键字以及其另一个关键信息是可以考虑使用哈希表相关的数据结构
LeetCode30-串联所有单词的子串-hard
因为题目所给words中可以存在重复的单词，所以我们选择可以同时储存key与value的哈希表用于保存于核验。再加上子串长度为words内所有单词总长，固定不变的长度加上遍历很容易联想到滑动窗口。所以总思路为滑动窗口+哈希表数据结构。
我们先将words存储在一个hash中，再遍历每次滑动后的窗口并用hash保存窗口内单词于其数量。注意窗口内的单词除了不存在于wors的情况还有窗口内同一单词出现次数多于words包含的数量。两种错误情况都要考虑到。下文有两种解法，第一种当时我绝对是犯病了，时空都高的离谱，作为错误示例吧，第二片代码为优化过。
优化前：
class Solution
{
public:
vector findSubstring(string s, vector &words)
{
int len = words[0].size();
map hash; //用于保存words内容
vector res;
for (int i = 0; i < words.size(); i++)
{
if (hash.count(words[i]))
hash.find(words[i])->second++;
else
hash.emplace(words[i], 1);
}
int Window = len * words.size();
for (int i = 0; i < 1 + s.size() - Window; i++)
{
string temp;
map hash0(hash);
//这篇代码的编程思路是每个窗口都重新开辟并且复制words的hash表
//然后每次遇到对应的单词进行数量递减，实属降智行为
bool flag = 1; //flag用于标记窗口内的单词是否有满足条件的，外层循环每次根据flag的值决定是否更新结果数组
for (int j = 0; j < Window; j++)
//遍历窗口内容，每走过一个单词的长度更新一次用于保存窗口内容的hash0
{
temp += s[i + j]; //用于保存当前检验的单词
if ((j + 1) % len == 0) //每次得到一个单词就进行一次检验
{
if (hash0.count(temp))
{
if (hash0.find(temp)->second >= 1)
hash0.find(temp)->second--;
else
{
//单词数量超出words包含数量
flag = 0;
break;
}
}
else //words中不存在该单词
{
flag = 0;
break;
}
temp.clear();
}
}
if (flag)
res.push_back(i);
}
return res;
}
};
优化后：
总体上思路一样的，细节处进行了优化，虽然耗时还是很高T-T
class Solution
{
public:
vector findSubstring(string s, vector &words)
{
int len = words[0].size();
map hash;
vector res;
for (int i = 0; i < words.size(); i++)
{
hash[words[i]]++;
}
map hash0;
//这次我们的hash0用来往里加入合适的单词，只需要开辟一次空间，重复使用就好了
int Window = len * words.size();
for (int i = 0; i < 1 + s.size() - Window; i++)
{
string temp;
bool flag = 1;
for (int j = len - 1; j < Window; j += len)
//根据单词长度跳着遍历，节省时间
{
temp = s.substr(i + j - len + 1, len);
if (hash[temp] == 0)
{
flag = 0;
break;
}
hash0[temp]++;
if (hash0[temp] > hash[temp])
{
flag = 0;
break;
}
temp.clear();
}
hash0.clear();
if (flag)
res.push_back(i);
}
return res;
}
};
LeetCode30-串联所有单词的子串-hard
如果抛去额外的时空限制，这题其实简单的不行，直接开个哈希表存储遍历就好了，但是这样会使用O(N)的空间不符合题意，笔者百思不得其解后打开了题解QWQ，看完第一种解法只想说一句：妙蛙种子吃着妙脆角妙进了米奇妙妙屋——妙到家了~；至于第二种解法其实很常规也很简单，没想到属实怪自己。
两种方法都参考了官方题解
本题带来的经验教训就是：对于限制使用常数空间时不要钻牛角尖不去考虑空间上的变换，我们既然不能新开辟一个数组，那么我们就把思维放在原数组上进行变换，达到我们要的结果。
**对于第一种解法：**本质上使用题目给的数组改装成为一个特殊的哈希表，首先我们要想清楚最终的结果只可能出现在[1-N+1]中，因为无非就两种情况，一种是数组中N个位置[1-N]所有数据都出现，那么最小就是N+1；其他所有情况获得结果都处于[1-N]之间。
想通这一点，我们再来考虑怎样用一个数组实现哈希表快速查找的功能：我们还是将每个位置的数值作为key，用key作为索引找到数组中对应的位置，在该位置上做一定的标记作为我们的flag，实现后我们就可以通过遍历改装后的数组，从0-N-1按照各个索引的flag判断最小的未出现过的正整数的位置！
当然还有一些细节就是预处理掉原数组中的非正整数，我们用一个大于N的数代替就好
class Solution
{
public:
int firstMissingPositive(vector &nums)
{
int len = nums.size(), temp;
for (int i = 0; i < len; i++) //预处理掉非正数
{
if (nums[i] <= 0)
nums[i] = len + 1;
}
for (int i = 0; i < len; i++) //构建“哈希表”
{
temp = abs(nums[i]);
if (temp < len + 1)
nums[temp - 1] = -abs(nums[temp - 1]);
}
for (int i = 0; i < len; i++) //遍历构建好的“哈希表”找出最终的结果
{
if (nums[i] > 0)
return i + 1;
}
return len + 1; //1-N所有数字都出现过，最小正整数为N+1
}
};
下面看第二种解法，说实话这种解法没想到属实是因为这种方法相关的题做的太少了。
先说思路：在原数组上对数据进行置换操作，将数据与索引对应起来，然后第二次遍历数组，遍历到索引与数据无法对应时我们就可以知道确实的第一个正数的结果了。
至于这个方法虽然使用了嵌套的循环，但是由于每次的交换操作都会使得某一个数交换到正确的位置，因此交换的次数最多为 N，整个方法的时间复杂度还是为 O(N)。
class Solution
{
public:
int firstMissingPositive(vector &nums)
{
int len = nums.size();
for (int i = 0; i < len; i++)
{
while (nums[i] <= len && nums[i] >= 1 && nums[i] != nums[nums[i] - 1])
//注意nums[i]!=nums[nums[i]-1]这个条件一定要有不然会出现死循环的情况
{
swap(nums[i], nums[nums[i] - 1]);
}
}
for (int i = 0; i < len; i++)
{
if (nums[i] != i + 1)
{
return i + 1;
}
}
return len + 1;
}
};
LeetCode76-最小覆盖子串-hard
最开始又想到滑动窗口，但是之前做题都是定长的窗口滑动，这次局限于思维定势了，看过题解才有中恍然大悟的感觉。
总思路为滑动窗口+哈希表：双指针规划出一个字串，递增窗口右指针，子串范围改变时更新窗口中子串的哈希表，同时与题给目标字符串进行比较，如果找到了满足要求的字串那我们就可以对另一个要求-“最短”进行子串范围的压缩，保持右指针不懂通过移动窗口的左指针向右移动，并不断判定。
参考自官方题解
class Solution
{
map window;
map hash;
public:
bool check() //判断当前窗口是否满足要求
{
for (auto p : hash)
{
if (p.second > window[p.first])
return false; //hash中所有的字符都拿出来做比较
}
return true;
}
string minWindow(string s, string t)
{
for (int i = 0; i < t.size(); i++)
{
hash[t[i]]++; //初始化t字符串的hash
}
int ansl = -1, len = INT16_MAX, l = 0, r = -1;
while (r < int(s.length()))
//string.size()和string.length()返回的是无符号int类型，平时在正数范围用不会出错
//但是本段代码种r初值-1如果直接与s.length()采用无符号数比较方法，那么实际上-1>s.length()因为符号位为1
{
if (hash.count(s[++r]))
window[s[r]]++;
//主线是依次递增r至s字符串的结尾
while (check() && l <= r)
//复线是对于当前的窗口进行判断，同时不断压缩窗口长度至不满足条件，满足条件时更新最优值
{
if (r - l + 1 < len)
{
ansl = l;
len = r - l + 1;
}
if (hash.count(s[l]))
window[s[l]]--;
l++;
}
}
return ansl == -1 ? string() : s.substr(ansl, len);
}
};
LeetCode12-整数转罗马数字-middle
有一说一这哈希表相关找来的题目和哈希表也没啥关系啊！
解法一：说一句暴力yyds（傻瓜写法）直接模拟的运算过程。
class Solution
{
public:
string intToRoman(int num)
{
string res;
while(num>=1000)
{
res+="M";
num-=1000;
}
if(num/900>0)
{
res+="CM";
num-=900;
}
if(num>=500)
{
res+="D";
num-=500;
}
while(num/400>0)
{
res+="CD";
num-=400;
}
while(num>=100)
{
res+="C";
num-=100;
}
if(num>=90)
{
res+="XC";
num-=90;
}
if(num>=50)
{
res+="L";
num-=50;
}
while(num>=40)
{
res+="XL";
num-=40;
}
while(num>=10)
{
res+="X";
num-=10;
}
if(num>=9)
{
res+="IX";
num-=90;
}
if(num>=5)
{
res+="V";
num-=5;
}
while(num>=4)
{
res+="IV";
num-=4;
}
while(num>=1)
{
res+="I";
num-=1;
}
return res;
}
};
解法二：循环的方式，减少代码量
class Solution
{
public:
string intToRoman(int num)
{
string res;
pair nums[] = {
{1000, "M"},
{900, "CM"},
{500, "D"},
{400, "CD"},
{100, "C"},
{90, "XC"},
{50, "L"},
{40, "XL"},
{10, "X"},
{9, "IX"},
{5, "V"},
{4, "IV"},
{1, "I"}};
int i = 0;
while (num > 0)
{
if (num >= nums[i].first)
{
int cnt = num / nums[i].first;
num -= cnt * nums[i].first;
while (cnt--)
res += nums[i].second;
}
i++;
}
return res;
}
};
