公司来了位阿里出来的高级开发，月薪3万+，才几天就离职了。他说以为降薪进来压力会小点，但领导觉得他是组里薪资最高的，应该承担更多

有个经典小题，口语说法就叫“在长串里找短串的所有排列出现的位置”。比如 s = "cbaebabacd"，p = "abc"，那答案是 [0, 6]，因为从 0 开始的 "cba" 和从 6 开始的 "bac" 都是 "abc" 的一种排列。听起来像暴力就能做，但一旦长度上去，暴力就不太行了。更靠谱的是滑动窗口，把“是否匹配”这件事压成常数时间去移动。

我们只关心 p 里每个字母要多少个。先用一个长度 26 的计数数组 cnt 记录 p 的需求，cnt[x] 是还差多少个字母 x。然后在 s 上维护一个定长窗口，长度固定为 p.length()。右指针进一个字符，就把它在 cnt 里减一；如果减之前这个位置是正的，说明这个字符正好补上了一个“缺口”，我们就把 need 减一。need 一开始是 p 的长度，代表还差多少个字符能完整匹配。当窗口长度达到 p 的长度时检查一下 need 是否为 0，是的话当前 left 就是答案之一。接着要把 left 往右挪，窗口左边的字符要“退回需求”：把它在 cnt 里加一；如果加完之后这个位置变成正数，说明我们又“缺”回来了一个字符，于是 need 加一。整个过程 right 一直往右扫一遍，时间就是 O(n)。

这一套的好处是窗口每次移动只做两次 O(1) 的更新，不会在窗口内部重复数数。注意我们默认都是小写字母，如果题目字符集更大，把数组换成哈希表就行。

import java.util.*;

publicclassFindAllAnagrams{
publicstatic List<Integer> findAnagrams(String s, String p){
        List<Integer> ans = new ArrayList<>();
if (s == null || p == null || s.length() < p.length()) return ans;

int[] cnt = newint[26];
for (char c : p.toCharArray()) cnt[c - 'a']++;

int need = p.length();
int left = 0, right = 0;
while (right < s.length()) {
int in = s.charAt(right) - 'a';
if (cnt[in] > 0) need--;
            cnt[in]--;
            right++;

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

// 小测一下
publicstaticvoidmain(String[] args){
        System.out.println(findAnagrams("cbaebabacd", "abc")); // [0, 6]
        System.out.println(findAnagrams("abab", "ab"));        // [0, 1, 2]
    }
}

一个是窗口必须“定长”，也就是 right 每进一个字符，当长度达到 p 的长度，就得把 left 推进一格，这样窗口里永远是 p.length() 个字符。另一个是 need 的维护别写反了：只有当某个字符的库存在进入前是正数，才说明它能真实地弥补缺口；反过来，左边出窗口时，只有在加回后变成正数，才代表又缺了一个。这个小判定让逻辑既准确又简单，不需要每次都去比较整个计数数组是否全为 0。

时间 O(|s|)，空间 O(1)（26 个字母时）。如果字符集是 ASCII，数组开到 128；如果是 Unicode 或者需要区分大小写、包含数字，就改用 HashMap<Character, Integer>，思想完全一样。再扩一步，如果题目让你找“至多 k 个不同字符的子串”之类的，滑动窗口也能照葫芦画瓢，把“是否满足约束”的判断压成 O(1) 的状态变量即可。

就这些，代码落地很稳，面试里也常见，写熟练了基本手到擒来。

-END-

我为大家打造了一份RPA教程，完全免费：songshuhezi.com/rpa.html