记录力扣--＞找到字符串中所有字母异位词

题目:

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

示例 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" 的异位词。

分析:什么是“字母异位词”？

        首先搞明白，题目要我们找 p 的字母异位词。什么是字母异位词？比如 p = "abc"，那么不管是 "abc"、"bca" 还是 "cab"，只要“包含的字母种类和每个字母的数量完全一模一样”，它们就是同胞兄弟。

怎么高效验证两个字符串里面装的字母和数量是不是完全一样呢？

做两个大小为 26 的“计数存钱罐”数组（sCount 和 pCount）。

• pCount 负责死死记录目标 p 的字母分布，一旦记好，这辈子都不再变了。

• sCount 则是我们的移动镜头缓存。

只要这两个数组长得完全一样（Arrays.equals(sCount, pCount)），就说明镜头里的这截字符串百分之百是 p 的异位词！

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

首先:先记录好两个字符串的长度,并定义一个集合来装我们返回的结果,有一点要注意,如果字符串p的长度大于字符串s的长度,那就说明不可能有异位词,直接返回空集合

int slen=s.length(),plen=p.length();
ArrayList<Integer> res= new ArrayList<>();
if(plen>slen){
return new ArrayList<Integer>();
}

之后,我们遍历字符串p,也就是固定窗口

for(int i=0;i<plen;i++){
sCount[s.charAt(i)-'a']++;
pCount[s.charAt(i)-'a']++;
}
if(Arrays.equals(sCount,pCount)){
list.add(0);
}

这里直接比较,如果现在两个数组相等,就说明前plen位的字符串是异位词

在集合中添加进去,第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)) {
res.add(i + 1); // 👈 为什么这里是加 i+1？
}
}

解释;这个 for 循环到底在干嘛

我们拿一个真实的场景来套：假设大字符串 s = "c b a e b a g"，我们的目标 p = "abc"（长度 plen = 3）。

🎬 步骤 1：开局先看前 3 个字符（第 0、1、2 位 ── "cba"）

在进入这个大循环之前，代码的第一个 for 循环已经把 s 的前 3 个字符 "cba" 收集进 sCount 存钱罐里了。

• 此时对比 Arrays.equals，发现 "cba" 的字母数量和 "abc" 完美对上。

• 于是 res.add(0)，记下第 0 位是一个好起点。

🎬 步骤 2：镜头开始往右匀速平移！进入那个困惑的循环

现在镜头要往右挪一格，去看看接下来的三个字符。现在的镜头应该从 "cba" 变成 "bae"。

请仔细盯着这两个相邻窗口的交替变化：

旧窗口：[c b a] e b a g

新窗口：c [b a e] b a g

发现了没有？从旧窗口变成新窗口，里面正中间的 "b a" 根本就没有变！整个镜头发生的变化只有两点：

这就是滑动窗口的至高境界：“只挪两头，不乱中间”！不管 p 的长度是一万还是十万，镜头每次往右挪一格，我都只需要做一次减法（吐出左边）、一次加法（吃进右边），而不需要把镜头里的字符重新数一遍！

🎬 步骤 3：为什么满足条件时，添加的是 i + 1？

因为刚才我们在处理 i = 0 的时候：

• 我们把旧的第 0 位（'c'）吐出去了。

• 把新的第 3 位（'e'）吃进来了。

• 此时镜头里的这截新字符串（"bae"），它的左起点已经变成了第 1 位（即 i + 1）！

• 如果这时候 Arrays.equals 判定成功，说明这个新镜头合格，它的起点是 1，所以代码自然要 res.add(i + 1)。

完整代码:

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[] sCount = new int[26];
int[] pCount = new int[26];

// 1. 初始化：先把开局最前面的 plen 长度的代码装进各自的存钱罐
for(int i = 0; i < plen; i++){
sCount[s.charAt(i) – 'a']++; // 收集 s 的开局前几个
pCount[p.charAt(i) – 'a']++; // 收集 p 的全部，以后作为标准答案不动了
}

// 2. 先看开局第一眼（第 0 位起步的窗口）合格不合格
if(Arrays.equals(sCount, pCount)){
res.add(0); // 合格就记下 0
}

// 3. 镜头开始匀速平移！i 代表刚刚被甩出镜头左边的那个人
for(int i = 0; i < sLen – plen; i++){
sCount[s.charAt(i) – 'a']–; // 🎯 吐出左边过期的旧字符
sCount[s.charAt(i + plen) – 'a']++; // 🎯 吃进右边刚刚踩到的新字符

// 4. 两头加减完后，当前的存钱罐对应的就是以 i+1 为起点的新窗口了
if (Arrays.equals(sCount, pCount)) {
res.add(i + 1); // 如果新窗口和标准答案一样，记下新起点 i+1
}
}
return res;
}
}