临沂网站建设电话,yahoo引擎入口,网站做服务端,买卖网交易平台题目
链接#xff1a;leetcode链接
思路分析#xff08;滑动窗口#xff09;
很容易想到#xff0c;这个题目要求我们在字符串s中找到一个定长的窗口让窗口里面出现异位词。
OK#xff0c;先思考一下怎么快速判断两个字符串是否是异位词#xff1f; 比较简单的方法是…题目
链接leetcode链接
思路分析滑动窗口
很容易想到这个题目要求我们在字符串s中找到一个定长的窗口让窗口里面出现异位词。
OK先思考一下怎么快速判断两个字符串是否是异位词 比较简单的方法是把字符串的每一个字符往哈希表里面丢然后比较哈希表即可。 异位词只关心字母的个数不关心顺序所以使用哈希表可以比较快速的判断。 记p为hash1s为hash2
然后我们只需要去维护一个定长的窗口去与p去比较即可。
OK 那么先leftright 0; 然后进窗口hash2[right] 当窗口的长度大于p的长度时开始出窗口 hash2[left]–left
当hash1 hash2 时就left即满足要求。
优化
注意这里hash表里面仅仅存的是字符总共26个小写字母直接遍历一遍出结果就可以还是很好比较的但是如果存的不是字符呢存的是字符串怎么办 这是再遍历hash去比较比较的麻烦。 这里提出一种可以优化的方案。
大体思路不变主要是优化hash表的比较。
我们增加一个变量count来记录窗口中的有效元素的个数。 我们在进窗口后和出窗口前都去维护这个count变量即可。
那么什么是有效元素呢 我们来举一个例子就以示例1为例 s “ccaebabacd” p “abc” 开始 hash2[s[right]] 进入hash表后1 hash1[c]那么这就是有效元素count right hash2[s[right]]进入hash表后2 hash1[c] 这就是无效元素count就不变
接着a入窗口有效元素count 接着e如窗口无效元素count不变
这时发现窗口长度超过了p的长度就需要出窗口 出窗口前发现hash2[left] 2 hash1[left]那么说明出的这个元素是无效元素count不需要改变 下一次出窗口时发现hash2[c] hash1[c]诶就是有效元素了count–
当count 3时left就是符合要求的下标。
代码
优化前代码 vectorint findAnagrams(string s, string p) {int hash1[26] {0},hash2[26] {0};int len p.size();vectorint v;for(auto e:p) {hash1[e-a];}for(int left 0,right 0;right s.size();right){char in s[right];hash2[in - a];if(right - left 1 len){char out s[left];hash2[out - a]--;left;}int i 0;for( i 0;i26;i){if(hash1[i]!hash2[i])break;}if( i 26)v.push_back(left);}return v;}优化后代码
vectorint findAnagrams(string s, string p) {int hash1[26] {0},hash2[26] {0};int len p.size();int count 0;vectorint v;for(auto e:p) {hash1[e-a];}for(int left 0,right 0;right s.size();right){char in s[right];hash2[in - a];if(hash2[in - a] hash1[in - a]){count;}if(right - left 1 len){char out s[left];if(hash2[out - a] hash1[out - a]) count--;hash2[out - a]--;left;}if(count len)v.push_back(left);}return v;}
