找到字符串中所有字母异位词问题

用户11458826

发布于 2025-01-23 17:04:29

4700

代码可运行

文章被收录于专栏：杀马特

运行总次数：0

代码可运行

一·题目简述：

leetcode题目链接：. - 力扣（LeetCode）

二·思路汇总：

哈希+滑动窗口：即窗口里就是固定的len（p）;然后比较两个hash表内数据是否完全对着上，如果是那么就保存left，依次循环进行下去。

这里画图说明一下步骤：

这里可以优化一下：

比如在建立hash的时候由于这里都是小写字母；故可以建立可放26个字母的hash（利用映射）

还有就是这里字母数量少，以及找的只是单个字母，如果要是单个字符串那么，这样再去遍历比较肯定特别麻烦，因此可以考虑在入出窗口的时候就保存count来记录这个窗口内本来有模版hash表内数据的有效字符的个数，画图解释一下：

这时此题的要点就差不多了。

三·解答代码：

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int n=s.size();
        vector<int> v;
        int hash_p[26]={0};//把p内数据映射入哈希表
        int hash_s[26]={0};//入到窗口的数据
        for(auto e:p){
            hash_p[e-'a']++;
        }
        int len=p.size();
     for(int left=0,right=0,count=0;right<n;right++){
              int in=s[right]-'a';//入窗口数据
              int out =s[left]-'a';//出窗口数据

              //入窗口：：
              hash_s[in]++;
              //这里如果后面直接遍历两个hash表比较，复杂度比较高，故选择开始入数据和出数据都完成记录。
              if(hash_s[in]<=hash_p[in]){
                count++;//记录有效字母的个数
              }
              //出窗口：
              if(right-left+1>len){
                 if(hash_s[out]<=hash_p[out]){
                    count--;
                }
                hash_s[out]--;
                left++;1
               
              }
              //出窗口后更新结果：
              if(count==len){
                v.emplace_back(left);
              }

     }
     return v;
    }
};

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2025-01-23，如有侵权请联系 cloudcommunity@tencent.com 删除

数据