杭州制作网站哪家好,东莞网络公司排行榜,营销型网站设计,企业对做营销型网站有什么优势Problem: 438. 找到字符串中所有字母异位词 438. 找到字符串中所有字母异位词 预备知识解题思路复杂度Code其它细节推荐博客或题目博客题目滑动窗口哈希表 预备知识 此题用到了双指针算法中的滑动窗口思想#xff0c;以及哈希表的运用。c中是unordered_map。如果对此不了解的u… Problem: 438. 找到字符串中所有字母异位词 438. 找到字符串中所有字母异位词 预备知识解题思路复杂度Code其它细节推荐博客或题目博客题目滑动窗口哈希表 预备知识 此题用到了双指针算法中的滑动窗口思想以及哈希表的运用。c中是unordered_map。如果对此不了解的uu建议查看相关介绍博客和更简单的题目
解题思路
该题解法为滑动窗口 哈希表。 该题的滑动窗口是固定的我们只需要对每次移动新字符和删除字符进行判断时间复杂度为O(n)。 首先定义一个哈希表记录要满足匹配p字符串需要多少的对应的字符。 unordered_mapchar, int pp;遍历p出现对应的字符就在该位置的–说明还需要在s中找多少该字符。 while (j p.size()) { //O(1) 理论上子字符串的操作应该是1//开始遍历在s上初始化第一个字符串能够满足对应字符供给的就pp[s[j]];
}遍历pp如果不为0说明该子字符串不满足匹配条件则跳到x. for (auto [a, b] : pp) { //O(1) max26//遍历pp如果不为0说明该子字符串不满足匹配条件则跳到xif (b ! 0) goto x;
}最后进行全局遍历 while (j s.size()) { //O(n)//开始遍历//对于j位置的字符将pp对应位置表示提供一个字符pp[s[j]];//对于i位置的字符将pp对应位置--表示不能提供一个字符pp[s[i]]--;for (auto [a, b] : pp) { //O(1) max26if (b ! 0) goto xx;}v.push_back(i 1);xx:;i;j;
}复杂度
时间复杂度: O(26 * n)26是遍历哈希表中的每种英文字母的个数最多为26n是遍历滑动窗口。 空间复杂度: O(26 n)26是哈希表最大sizen是vector最大size。 Code
class Solution {
public:vectorint findAnagrams(string s, string p) {//记录要满足匹配p字符串需要多少的对应的字符unordered_mapchar, int pp; vectorint v;int i 0, j 0;for (auto a : p) { //O(n)//遍历p出现对应的字符就在该位置的--说明还需要多少该字符pp[a]--;}while (j p.size()) { //O(1) 理论上子字符串的操作应该是1//开始遍历在s上初始化第一个字符串能够满足对应字符供给的就pp[s[j]];}for (auto [a, b] : pp) { //调试bug的时候可以用输出的方法cout a b endl;}for (auto [a, b] : pp) { //O(1) max26//遍历pp如果不为0说明该子字符串不满足匹配条件则跳到xif (b ! 0) goto x;}v.push_back(i);x:;while (j s.size()) { //O(n)//开始遍历//对于j位置的字符将pp对应位置表示提供一个字符pp[s[j]];//对于i位置的字符将pp对应位置--表示不能提供一个字符pp[s[i]]--;for (auto [a, b] : pp) { //O(1) max26if (b ! 0) goto xx;}v.push_back(i 1);xx:;i;j;}return v;}
};其它细节
可以尝试用输出日志的方式来获得局部代码的正确性。对于比较长的代码我们应该在写完整个代码之前已经完成多个地方的日志输出。多加练习能够提高自己写代码的正确性。
for (auto [a, b] : pp) { //调试bug的时候可以用输出的方法cout a b endl;
}推荐博客或题目
博客
滑动窗口详解哈希表理论基础
题目
滑动窗口
无重复字符的最长子串 难度
哈希表
两数之和 难度三数之和 难度四数之和 难度四数相和II 难度
