LeetCode LCR 015. 找到字符串中所有字母异位词

Categories:

题目描述
思路分析
1. 解法一：滑动窗口 + 计数（推荐）
相似题目

题目描述

✅ LCR 015. 找到字符串中所有字母异位词

思路分析

解法一：滑动窗口 + 计数（推荐）

核心思路：

用长度为 26 的计数数组记录模式串 p 的字符需求。

右指针扩展窗口，左指针收缩保持窗口长度为 p.length()。

当窗口内所有字符都满足需求时，记录起始位置。

复杂度分析：

时间复杂度：O(n)，其中 n 为 s 的长度。

空间复杂度：O(1)，字符集大小固定。

class Solution {
    public List<Integer> findAnagrams(String s, String p) {
        List<Integer> ans = new ArrayList<>();
        if (s.length() < p.length()) {
            return ans;
        }

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

        int left = 0;
        int need = p.length();

        // 滑动窗口保持长度为 p.length()
        for (int right = 0; right < s.length(); right++) {
            int r = s.charAt(right) - 'a';
            if (cnt[r] > 0) {
                need--;
            }
            cnt[r]--;

            if (right - left + 1 == p.length()) {
                if (need == 0) {
                    ans.add(left);
                }
                int l = s.charAt(left) - 'a';
                if (cnt[l] >= 0) {
                    need++;
                }
                cnt[l]++;
                left++;
            }
        }

        return ans;
    }
}

func findAnagrams(s string, p string) []int {
    ans := make([]int, 0)
    if len(s) < len(p) {
        return ans
    }

    cnt := make([]int, 26)
    for i := 0; i < len(p); i++ {
        cnt[p[i]-'a']++
    }

    left := 0
    need := len(p)

    // 滑动窗口保持长度为 len(p)
    for right := 0; right < len(s); right++ {
        r := s[right] - 'a'
        if cnt[r] > 0 {
            need--
        }
        cnt[r]--

        if right-left+1 == len(p) {
            if need == 0 {
                ans = append(ans, left)
            }
            l := s[left] - 'a'
            if cnt[l] >= 0 {
                need++
            }
            cnt[l]++
            left++
        }
    }

    return ans
}

相似题目

题目	难度	考察点
76. 最小覆盖子串	困难	滑动窗口
567. 字符串的排列	中等	滑动窗口
3. 无重复字符的最长子串	中等	滑动窗口
30. 串联所有单词的子串	困难	滑动窗口
242. 有效的字母异位词	简单	计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2026/29341602