当前位置：首页 > news >正文

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

news 2025/6/13 19:28:54

继续每日一题，今天给大家带来一道非常经典的滑动窗口类型的题目，掌握该题，基本滑动窗口类型的题目都可以迎刃而解

题目描述

给定两个字符串 s 和 p，找到 s 中所有 p 的异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

题目示例：
在这里插入图片描述

这道题考察的就是滑动窗口的基本用法，针对滑动窗口类型的题目，有一个固定思路：

1.确定窗口的左右边界一般定义两个指针：left right来指向窗口的最左侧和最右侧

2.滑动窗口，在滑动的过程中，需要移动左右指针，在移动的过程中我们只需要关注一个操作：

移动右指针，添加元素
移动左指针，删除元素

对于本题，以题目中的case为例

s = “cbaebabacd”, p = “abc”

初始化窗口边界：left=0,right=0

此时窗口大小1，窗口内容：c
- 窗口大小=1<p.length，移动右指针
left=0,right=1，窗口内容：cb
- 窗口大小=2<p.length，移动右指针
left=0,right=2，窗口内容：cba
- 窗口大小=3=p.length，比较窗口内容和p，是异位词，将left加入结果集

遇到窗口大小和待比较值长度一致后，我们接下来要做的就是移动左指针，去滑动窗口，此处有个点需要我们注意，左右指针指向的一定窗口的边界值，所以移动左指针，还需要将窗口里左指针指向的元素移除

此时left=1,right=2，窗口内容：ba
- 窗口大小=2<p.length，移动右指针
left=1,right=3，窗口内容：bae
- 窗口大小=3=p.length，比较窗口内容和p，不是异位词，移动左指针
left=2,right=3，窗口内容：ae
- 窗口大小=2<p.length，移动右指针
left=2,right=4，窗口内容：aeb
- 窗口大小=3<p.length，移动右指针,比较窗口内容和p，不是异位词，移动左指针

后面的元素一样，都是按照上面的步骤处理

里面还有一个比较点，如果处理不好，也会比较耗时，就是如何判断两个字符串是否为异位词，异位词的标准就是字符串长度以及每次字母出现的次数是一样的，我们可以两个数组：

int[] pCount = new int[26];
int[] windowCount = new int[26];
利用：Arrays.equals(windowCount, pCount)去比较

最终实现如下：

    public static List<Integer> findAnagrams1(String s, String p) {int[] pCount = new int[26];for (Character c : p.toCharArray()) {pCount[c - 'a']++;}int left = 0, right = 0;List<Integer> result = new ArrayList<>();int[] windowCount = new int[26];StringBuilder sb = new StringBuilder();while (right <= s.length()) {if (sb.length() == p.length()) {//比较是否相等if (Arrays.equals(windowCount, pCount)) {result.add(left);}sb.delete(0, 1);windowCount[s.charAt(left) - 'a']--;left++;} else if (right < s.length()) {sb.append(s.charAt(right));windowCount[s.charAt(right) - 'a']++;right++;} else break;}return result;}