leet hot 100-9 找到字符串中所有字母异位词

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

• 原题链接
• 思路
• 代码

  原题链接

  leet hot 100-9

  438. 找到字符串中所有字母异位词

  

  思路

  声明一个无序map容器，容器里面记录着目标 p 里面所有字母出现的次数。

  遍历整个数组 每次把当前元素在容器中的次数减去1 表示这个当前维护的窗口里面s[i] 的次数需要满足的点-1，然后查看当前的窗口的大小是否大于指定的p的大小 只有窗口大小等于p的大小才能查看窗口里面的值是否全部满足条件，如果要大于窗口里面的值 需要将j往后面走 就从新把条件收回 如果cnt[j] 表示需要满足的条件j这一位 如果刚好满足 但是窗口要减小了 它不满足了 就要收回相关的满足条件 只到把窗口调整为p的大小
  最后再查看一下满足的条件 是否等于p中不同字母的数量

  ---

  时间复杂度O(n) 空间复杂度(n)

  代码

  class Solution {
  public:
      vector findAnagrams(string s, string p) {
          unordered_map st;
          for(auto c: p) st[c]++; //记录p中出现的位置和下标
          int tol = st.size(); //表示p的数量大小
          vector res;
          for(int i =0 ,j= 0 ,satisfy  =0 ;i p.size())
              {
                  if(st[s[j]] == 0) satisfy--;
                  st[s[j]]++;
                  j++;
              }
              if(satisfy == tol) res.push_back(j);
          }
          return res;
      }
  };