【Day 45 】2022-12-15 - 438. 找到字符串中所有字母异位词

[azl397985856]

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

入选理由

暂无

题目地址

https://leetcode-cn.com/problems/find-all-anagrams-in-a-string/

前置知识

• Sliding Window
• 哈希表

  题目描述

  
  给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。 不考虑答案输出的顺序。 示例 1:

输入: s: "cbaebabacd" p: "abc"

输出: [0, 6]

解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。 示例 2:

输入: s: "abab" p: "ab"

输出: [0, 1, 2]

解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的字母异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的字母异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的字母异位词。

[testplm]

import collections
class Solution:
    def findAnagrams(self, s, p):
        # 统计p的各个字母数量
        myDictP=collections.Counter(p)
        myDictS=collections.Counter(s[:len(p)])
        output=[]
        i=0
        j=len(p)

        while j<=len(s):
            # 如果字母频率组成相同，则记下当前索引
            if myDictS==myDictP:
                output.append(i)
            # 最左边的字母出现次数-1
            myDictS[s[i]]-=1
            if myDictS[s[i]]<=0:
                myDictS.pop(s[i])

            if j<len(s):    
                 myDictS[s[j]]+=1
            j+=1
            i+=1

        return output

• Time:O(n)
• Space:O(1)

[snmyj]

public List<Integer> findAnagrams(String s, String p) {
    int sLen = s.length();
    int pLen = p.length();
    List<Integer> res = new ArrayList<>();
    int[] pCounts = new int[26];
    for (int i = 0; i < pLen; i++) {
        pCounts[p.charAt(i) - 'a']++;
    }

    int left = 0;
    int right = 0;
    while (right < sLen) 
        int inWin = s.charAt(right) - 'a'
        pCounts[inWin]--;
        while (pCounts[inWin] < 0) {
            int outWin = s.charAt(left++) - 'a';
            pCounts[outWin]++;
        }

        if (right - left + 1 == pLen) {
            res.add(left);
        }

        right++;
    }

    return res;

}

[ringo1597]

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

[arinzz]

class Solution { public: vector findAnagrams(string s, string p) { int n = s.size(), m = p.size(); vector pre(n + 1); vector res; int64_t sum = accumulate(p.begin(), p.end(), 0ll, [](int64_t cur, char c) { return cur + c c c; }); for (int i = 1; i <= n; i ++) { pre[i] = pre[i - 1] + s[i - 1] s[i - 1] s[i - 1]; } for (int i = m; i <= n; i ++) { if (sum == pre[i] - pre[i - m]) { res.push_back(i - m); } } return res; } };

[buer1121]

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]:

滑动窗口

    n,m=len(s),len(p)

    cnt=collections.Counter(p)
    need=m
    res=[]
    for right in range(n):
        ch=s[right]
        if ch in cnt:
            if cnt[ch]>0:
                need-=1
            cnt[ch]-=1

        left=right-m
        if left>=0:
            ch=s[left]
            if ch in cnt:
                if cnt[ch]>=0:
                    need+=1
                cnt[ch]+=1

        if need==0:
            # res.append(right-m+1)
            res.append(left+1)

    return res

[luhaoling]

class Solution { public: vector findAnagrams(string s, string t) { unordered_map<char, int> need, window; for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    vector<int> res; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c])
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == need.size())
                res.push_back(left);
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

};

[mayloveless]

思路

从头遍历每m个字母是否是异位词，通过滑动窗口遍历所有。检测方法：每个字母计数，相同长度的字符串，如果字母个数也相同，则是异位词。

代码

var findAnagrams = function(s, p) {
    const n = s.length
    const m = p.length
    if (m > n) {
        return [] 
    }
    const needs = new Array(26).fill(0)
    for (let i = 0; i < m; ++i) {
        needs[charCodeSubA(p[i])]++
    }

    const matched = new Array(26).fill(0)
    let startp = 0
    let endp = 0
    const result = []
    while (endp < m) {
        matched[charCodeSubA(s[endp])]++
        endp++ 
    }
    if (same(needs, matched)) {
        result.push(startp)
    }

    while (endp < n && startp < n) {
        matched[charCodeSubA(s[startp])]--
        matched[charCodeSubA(s[endp])]++
        startp++
        endp++
        if (same(needs, matched)) {
            result.push(startp)
        }
    }

    return result;
};

var charCodeSubA = a => a.charCodeAt(0) - 'a'.charCodeAt(0)

var same = (needs, matched) => {
    for (let i = 0; i < needs.length; ++i) {
        if (needs[i] !== matched[i]) {
            return false
        } 
    }   
    return true 
}

复杂度

时间：O(n+m) 空间：O(C) 26个字母

[FlipN9]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> result = new ArrayList<>();
        int len = p.length();

        int digitsNeed = len;
        int[] freq = new int[26];
        for (int i = 0; i < len; i++) {
            freq[p.charAt(i) - 'a']++;
        }

        int left = 0;
        for (int right = 0; right < s.length(); right++) {
            /* ------------左侧收缩------------ */
            while (right - left >= len) {
                char cl = s.charAt(left);
                if (freq[cl - 'a'] >= 0) {
                    digitsNeed++;
                }
                freq[cl - 'a'] ++;
                left++;
            }
            /* ------------右侧更新------------ */
            char cr = s.charAt(right);
            freq[cr - 'a']--;
            if (freq[cr - 'a'] >= 0) {
                digitsNeed--;
            }
            /* ------------添加结果------------ */
            if (digitsNeed == 0) {
                result.add(left);
            }
        }
        return result;
    }
}

[A-pricity]

/**
 * @param {string} s
 * @param {string} p
 * @return {number[]}
 */
//写法1
var findAnagrams = function (s, p) {
    let need = {};//需要的字符
    let win = {};//窗口中的字符
    for (let a of p) {//统计异位词的数量
        need[a] = (need[a] || 0) + 1;
    }
    //左右指针
    let left = 0,
        right = 0;
    let val = 0;//窗口中和need中字符数量一致的字符种类
    let res = [];
    while (right < s.length) {
        let c = s[right];
        right++;//右边的字符进入窗口
        if (need[c]) {
            win[c] = (win[c] || 0) + 1;//当前字符在need中，更新窗口中的字符数量
            if (win[c] == need[c]) {
                val++;//该字符在窗口中和need中的字符匹配时，字符种类+1
            }
        }
        while (right - left >= p.length) {//不断出窗口
            if (val == Object.keys(need).length) {//如果此时窗口中的子串和p是异位词则将左边界加入res中
                res.push(left);
            }
            let d = s[left];
            left++;//出窗口
            if (need[d]) {//如果该字符在need中 更新窗口中的字符数量 和字符种类
                if (win[d] == need[d]) {
                    val--;
                }
                win[d]--;
            }
        }
    }
    return res;
};

[Alyenor]

function findAnagrams(s: string, p: string): number[] {
    const m=new Map<string,number>()
    for(let i=0;i<p.length;i++){
        m.set(p[i],1+(m.has(p[i])?m.get(p[i]):0))
    }
    let l=0,r=0,res=[]
    while(r<p.length){
        if(m.has(s[r])){
            m.set(s[r],m.get(s[r])-1)
        }
        r++
    }
    const vs = Array.from(m).map(m=>m[1])
    if(vs.every(item=>item===0)) res.push(l)
    while(r<s.length){
        if(m.has(s[l])) m.set(s[l],1+(m.has(s[l])?m.get(s[l]):0))
        l++
        if(m.has(s[r])) m.set(s[r],m.get(s[r])-1)
        r++
        const vs = Array.from(m).map(m=>m[1])
        if(vs.every(item=>item===0)) res.push(l)
    }
    return res
};

[yuxiangdev]

class Solution { public List findAnagrams(String s, String p) { List result = new ArrayList<>(); int len = p.length();

    int digitsNeed = len;
    int[] freq = new int[26];
    for (int i = 0; i < len; i++) {
        freq[p.charAt(i) - 'a']++;
    }

    int left = 0;
    for (int right = 0; right < s.length(); right++) {
        /* ------------左侧收缩------------ */
        while (right - left >= len) {
            char cl = s.charAt(left);
            if (freq[cl - 'a'] >= 0) {
                digitsNeed++;
            }
            freq[cl - 'a'] ++;
            left++;
        }
        /* ------------右侧更新------------ */
        char cr = s.charAt(right);
        freq[cr - 'a']--;
        if (freq[cr - 'a'] >= 0) {
            digitsNeed--;
        }
        /* ------------添加结果------------ */
        if (digitsNeed == 0) {
            result.add(left);
        }
    }
    return result;
}

}

[chenming-cao]

解题思路

滑动窗口。用长度为26的数组记录字符串p中每个字符出现的次数。然后设置宽度为字符串长度p.length()的滑动窗口，求出字符串s出现在滑动窗口内的各个字符串出现次数，记录到数组中。如果该数组和字符串p的数组相等，则表示异位词出现。

代码

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int slen = s.length();
        int plen = p.length();
        List<Integer> res = new ArrayList<>();
        if (slen < plen) return res;
        int[] letters = new int[26];
        for (char c : p.toCharArray()) {
            letters[c - 'a']++;
        }
        String pletters = Arrays.toString(letters);     
        int[] word = new int[26];
        for (int i = 0; i < plen; i++) {
            word[s.charAt(i) - 'a']++;
        }
        if (Arrays.equals(letters, word)) res.add(0);
        for (int i = 1; i <= slen - plen; i++) {
            int pre = s.charAt(i - 1) - 'a';
            int post = s.charAt(i + plen - 1) - 'a';
            word[pre]--;
            word[post]++;
            if (Arrays.equals(letters, word)) res.add(i);
        }
        return res;
    }
}

复杂度分析

• 时间复杂度：O(n)，n为s的长度
• 空间复杂度：O(1)，需要两个长度为26的数组

[zywang0]

public List<Integer> findAnagrams(String s, String p) {
    int sLen = s.length();
    int pLen = p.length();
    List<Integer> res = new ArrayList<>();
    int[] pCounts = new int[26];
    for (int i = 0; i < pLen; i++) {
        pCounts[p.charAt(i) - 'a']++;
    }

    int left = 0;
    int right = 0;
    while (right < sLen) 
        int inWin = s.charAt(right) - 'a'
        pCounts[inWin]--;
        while (pCounts[inWin] < 0) {
            int outWin = s.charAt(left++) - 'a';
            pCounts[outWin]++;
        }

        if (right - left + 1 == pLen) {
            res.add(left);
        }

        right++;
    }

    return res;
}

[Jetery]

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

思路

使用数组来标记字母出现次数, 之后使用滑动窗口来记录定长下的字母频率

代码 (cpp)

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int m = s.size(), n = p.size();
        vector<int> ans;
        if (n > m) return ans;
        vector<int> ss(26, 0);
        vector<int> pp(26, 0);
        for (int i = 0; i < n; i++) {
            ss[s[i] - 'a']++;
            pp[p[i] - 'a']++;
        }
        if(ss == pp) ans.push_back(0);
        for (int i = n; i < m; i++) {
            ss[s[i - n] - 'a']--;
            ss[s[i] - 'a']++;
            if (ss == pp) ans.push_back(i - n + 1);
        }
        return ans;
    }
};

复杂度分析

• 时间复杂度：O(n)
• 空间复杂度：O(1)

[tiandao043]

思路

开始没想明白怎么计算相同，以为得排序，其实可以用cnt和全0的比。 滑动窗口

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        vector<int> ans;
        vector<int> cnt(26);
        vector<int> zero(26);
        for(auto &c:p){
            cnt[c-'a']++;
        }
        int l=0,r=0;
        int len=p.length();
        while(r<s.length()){
            if(r-l<len){
                cnt[s[r++]-'a']--;
            }else if(r-l==len){
                if(cnt==zero){
                    ans.push_back(l);
                }
                cnt[s[l++]-'a']++;
            }else{

            }
        }
        // cout<<cnt[s[s.length()-1]-'a']<<endl;
        if(cnt==zero){
                    ans.push_back(l);
                }
        return ans;
    }
};

O(n) O(1)

[BruceZhang-utf-8]

思路

• 滑动窗口

关键点

代码

• 语言支持：Java

Java Code:

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
List<Integer> res = new ArrayList<>();
        int sLen = s.length(), pLen = p.length();
        if (sLen < pLen) {
            return res;
        }
        int[] count = new int[26];
        for (int i = 0; i < pLen; ++i) {
            count[s.charAt(i) - 'a']++;
            count[p.charAt(i) - 'a']--;
        }
        int differ = 0;
        for (int i = 0; i < count.length; ++i) {
            if (count[i] != 0) {
                differ++;
            }
        }
        if (differ == 0) {
            res.add(0);
        }
        for (int i = 0; i < sLen - pLen; ++i) {
            // 去除当前字母的影响前，
            if (count[s.charAt(i) - 'a'] == 1) {
                differ--;
            } else if (count[s.charAt(i) - 'a'] == 0) {
                differ++;
            }
            // 去除当前字母的影响
            count[s.charAt(i) - 'a']--;
            // 窗口向后移动一个位置前
            if (count[s.charAt(i + pLen) - 'a'] == -1) {
                differ--;
            } else if (count[s.charAt(i + pLen) - 'a'] == 0) {
                differ++;
            }
            // 窗口向后移动一个位置
            count[s.charAt(i + pLen) - 'a']++;
            if (differ == 0) {
                res.add(i + 1);
            }
        }
        return res;
    }
}

[klspta]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        char[] str = s.toCharArray();
        char[] ptn = p.toCharArray();

        int[] sCount = new int[26];
        int[] pCount = new int[26];

        List<Integer> ans = new ArrayList<>();

        for(int i = 0; i < ptn.length; i++){
            pCount[ptn[i] - 'a']++;
            sCount[str[i] - 'a']++;
        }

        if(Arrays.equals(sCount, pCount)){
            ans.add(0);
        }

        for(int i = 0; i < str.length - ptn.length; i++){
            sCount[str[i] - 'a']--;
            sCount[str[i + ptn.length] - 'a']++;
            if(Arrays.equals(sCount, pCount)){
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

[RestlessBreeze]

思路

滑动窗口

代码

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();

        if (sLen < pLen) {
            return vector<int>();
        }

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }

        if (sCount == pCount) {
            ans.emplace_back(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if (sCount == pCount) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};

[paopaohua]

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        int sLen = s.size(), pLen = p.size();

        if (sLen < pLen) {
            return vector<int>();
        }

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s[i] - 'a'];
            ++pCount[p[i] - 'a'];
        }

        if (sCount == pCount) {
            ans.emplace_back(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s[i] - 'a'];
            ++sCount[s[i + pLen] - 'a'];

            if (sCount == pCount) {
                ans.emplace_back(i + 1);
            }
        }

        return ans;
    }
};

[ggmybro]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> list = new ArrayList<>();
        if(s.length() < p.length()){
            return list;
        }
        int[] target = new int[26];
        for(int i = 0; i < p.length(); i++){
            target[p.charAt(i) - 'a']++;
        }
        int left = 0;
        int right = 0;
        while(right < s.length()){
            target[s.charAt(right) - 'a']--;
            while(target[s.charAt(right) - 'a'] < 0){
                target[s.charAt(left) - 'a']++;
                left++;
            }
            if(right - left + 1 == p.length()){
                list.add(left);
            }
            right++;
        }
        return list;
    }
}

[wtdcai]

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        n, m, res = len(s), len(p), []
        if n < m: return res
        p_cnt = [0] * 26
        s_cnt = [0] * 26

        for i in range(m):
            p_cnt[ord(p[i]) - ord('a')] += 1

        left = 0
        for right in range(n):
            cur_right = ord(s[right]) - ord('a')
            s_cnt[cur_right] += 1
            while s_cnt[cur_right] > p_cnt[cur_right]:
                cur_left = ord(s[left]) - ord('a')
                s_cnt[cur_left] -= 1
                left += 1
            if right - left + 1 == m:
                res.append(left)
        return res

[AtaraxyAdong]

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        int sLen = s.length(), pLen = p.length();

        if (sLen < pLen) {
            return new ArrayList<Integer>();
        }

        List<Integer> ans = new ArrayList<Integer>();
        int[] sCount = new int[26];
        int[] pCount = new int[26];
        for (int i = 0; i < pLen; ++i) {
            ++sCount[s.charAt(i) - 'a'];
            ++pCount[p.charAt(i) - 'a'];
        }

        if (Arrays.equals(sCount, pCount)) {
            ans.add(0);
        }

        for (int i = 0; i < sLen - pLen; ++i) {
            --sCount[s.charAt(i) - 'a'];
            ++sCount[s.charAt(i + pLen) - 'a'];

            if (Arrays.equals(sCount, pCount)) {
                ans.add(i + 1);
            }
        }

        return ans;
    }
}

[whoam-challenge]

class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: s_len, p_len = len(s), len(p)

    if s_len < p_len:
        return []

    ans = []
    s_count = [0] * 26
    p_count = [0] * 26
    for i in range(p_len):
        s_count[ord(s[i]) - 97] += 1
        p_count[ord(p[i]) - 97] += 1

    if s_count == p_count:
        ans.append(0)

    for i in range(s_len - p_len):
        s_count[ord(s[i]) - 97] -= 1
        s_count[ord(s[i + p_len]) - 97] += 1

        if s_count == p_count:
            ans.append(i + 1)

    return ans

[MaylingLin]

思路

---

哈希表+滑动窗口。value为0时，移除key，哈希表容量为0时，说明找到了一个异位词。

代码

class Solution:
    def findAnagrams(self, s: str, p: str) -> List[int]:
        target = collections.Counter(p)  # Counter(计数器)追踪值的出现次数，用字典存储(key=值，value=出现次数)
        ans = []
        for i in range(len(s)):
            if i >= len(p):
                target[s[i - len(p)]] += 1
                if target[s[i - len(p)]] == 0:
                    del target[s[i - len(p)]]  # 列表操作，删除一个或几个元素
            target[s[i]] -= 1
            if target[s[i]] == 0:
                del target[s[i]]
            if len(target) == 0:
                ans.append(i - len(p) + 1)
        return ans

复杂度

---

• Time: $O(n)$，s长度为n
• Space: $O(1)$

[saitoChen]

思路

1. 当s < p时，一定不存在异位词
2. 窗口的大小就是p的长度，比较p中每个单词的数量和窗口中单词的数量是否相等

代码

const findAnagrams = (s, p) => {
  let slen = s.length, plen = p.length
  if (slen < plen) return []

  let result = []
  // 26个字母的个数
  const countS = new Array(26).fill(0)
  const countP = new Array(26).fill(0)
  for (let i = 0; i < plen; i++) {
    countS[s[i].charAtCode() - 'a'.charAtCode()]++
    countP[p[i].charAtCode() - 'a'.charAtCode()]++
  }
  if (countS.toString() === countP.toString()) {
    result.push(0)
  }

  for(let i = 0; i < slen - plen; i++) {
    // --是因为已经比较过了，需要还原
    countS[s[i].charAtCode() - 'a'.charAtCode()]--
    countS[s[i + plen].charAtCode() - 'a'.charAtCode()]++

    if(countS.toString() === countP.toString()) {
      result.push(i + 1)
    }
  }
  return result
}

复杂度分析

时间复杂度：O(N)

[xuanaxuan]

思路

• 字母异位词：不关心 p 这个串的顺序，只关心字母是否出现以及出现的次数，因此符合要求的子串长度都是 p，因而可以确定滑动窗口为固定长度p.length
• 滑动窗口：核心思想还是新窗口元素和 = 旧窗口元素和 - 左边移除的元素 + 右边进来的元素；
  • 如何存储 p 串及更新窗口信息：桶或哈希（数组ch），左出右进=桶中字符个数的增减
  • 用左右指针start,end 表示窗口的指向
  • 用rest来表示剩余待匹配字符的个数，并在循环过程维护，后续就不需要再去遍历ch判断是否字符个数都为0

let findAnagrams = function (s, p) {
   const res=[],aNum='a'.charCodeAt(0)
    if (s == null || p == null || s.length < p.length)
        return res;

    let ch = new Array(26).fill(0);
    //统计p串字符个数
    for (const c of p){
      ch[c.charCodeAt(0) - aNum]++;
    }

    //把窗口扩成p串的长度
    let  start = 0, end = 0, rest = p.length;
    for (; end < p.length; end++) {
      // 说明之前这个字母有在p中
      if (ch[s.charCodeAt(end)-aNum] >= 1)
          rest--;
        ch[s.charCodeAt(end)-aNum]--;
    }

    if (rest == 0)
        res.push(0);
    //开始一步一步向右移动窗口。
    while (end < s.length) {
        const l=s.charCodeAt(start)-aNum
        //左边的拿出来一个并更新状态
        ch[l]++;
        start++;
        //如果是不需要的字符，此时应该为0，毕竟在前面减过一次ch[l]
        if (ch[l] >= 1)  rest++;
        //右边的拿进来一个并更新状态
        const r=s.charCodeAt(end)-aNum
        if (ch[r] >= 1)  rest--;
        ch[r]--;
        end++;
        // 状态合法就存到结果集合
        if (rest == 0)
            res.push(start);
    }

    return res;
};

复杂度

时间复杂度：O(n)

空间：O(1)

[bookyue]

code

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        if (p.length() > s.length()) return List.of();

        List<Integer> ans = new ArrayList<>();

        int[] counts = new int[26];
        for (int i = 0; i < p.length(); i++) {
            counts[p.charAt(i) - 'a']++;
            counts[s.charAt(i) - 'a']--;
        }

        if (allZero(counts)) ans.add(0);

        for (int i = 0; i < s.length() - p.length(); i++) {
            counts[s.charAt(i) - 'a']++; // pull out
            counts[s.charAt(i + p.length()) - 'a']--; // push in
            if (allZero(counts)) ans.add(i + 1);
        }

        return ans;
    }

    private boolean allZero(int[] counts) {
        for (int c : counts)
            if (c != 0) return false;

        return true;
    }
}

[Ryanbaiyansong]

''' 理解题意: 两个string s 和 p, 返回所有start index of p 的anagram in s 维护一个长度为size p的窗口, 如果窗口内的所有字符满足了p的要求, 即count = need, 左指针j的位置就满足了答案 ''' class Solution: def findAnagrams(self, s: str, p: str) -> List[int]: need = Counter(p) window = defaultdict(int) res = [] n = len(s) unique = j = 0 for i, ch in enumerate(s): window[ch] += 1 if ch in need and window[ch] == need[ch]: unique += 1 while j < n and i-j+1 > len(p): if s[j] in need and window[s[j]] == need[s[j]]: unique -= 1 window[s[j]]-=1 j += 1 if i - j + 1 == len(p) and unique == len(need): res.append(j)

    return res

[chiehw]

基本思路：

• 滑动窗口

大致步骤：

1. 打表
2. 初始化窗口。
3. 移动窗口。

代码：

class Solution {
private:
    int sLen;
    int pLen;
    void initCount(string &s, string &p, vector<int> &sCount, vector<int> &pCount){
        for(int i=0; i<pLen; i++){
            sCount[s[i] - 'a']++;
            pCount[p[i] - 'a']++;
        }
    }
public:
    vector<int> findAnagrams(string s, string p) {
        sLen = s.size();
        pLen = p.size();
        if(sLen < pLen){
            return vector<int>();
        }

        vector<int> ans;
        vector<int> sCount(26);
        vector<int> pCount(26);
        initCount(s, p, sCount, pCount);

        if(sCount == pCount){
            ans.emplace_back(0);
        }
        for(int i=0; i<sLen-pLen; i++){
            sCount[s[i] - 'a']--;
            sCount[s[i+pLen] - 'a']++;

            if(sCount == pCount){
                ans.emplace_back(i+1);
            }
        }
        return ans;
    }
};

复杂度分析：

• 时间复杂度：O(n)
• 空间复杂度：O(1)