LeetCode查找字符串所有异位词Java代码报TLE如何优化

• 需求：编写Java代码实现功能：在给定字符串s中，找到所有是字符串p的异位词的子串，返回这些子串的起始索引
• 现存问题：自行编写的代码逻辑自认为正确，但提交运行时触发*TLE（超时）*错误，无法通过全部测试用例
• 原始提交代码如下：

class Solution {
public List<Integer> findAnagrams(String s, String p) {
    int[] fors=new int[26];
    int[] forp=new int[26];
    for(int i=0;i<p.length();i++){
        forp[p.charAt(i)-'a']++;
    }
    int k=p.length();
    int len=s.length();
    int i=0;
    int j=0;
    ArrayList<Integer> list=new ArrayList<>();
    if(s.length()<p.length()) return list;
    while(j<len){
        fors[s.charAt(j)-'a']++;
        if(j-i+1<k)j++;
        if(j-i+1==k){
            if(areSame(fors,forp)){
                list.add(j-k+1);
                fors[s.charAt(i)-'a']--;
                i++;
                j++;
            }
        }   
    }
    return list;   
}
public boolean areSame(int[] countS, int[] countP){
for(int i=0;i<26;i++){
    if(countS[i]!=countP[i]){
        return false;
    }
}
return true;
}
}

• 核心问题是滑动窗口逻辑存在死循环：当窗口长度达到k、但当前窗口内容和p不构成异位词时，代码没有任何移动指针的操作，会停在当前位置反复执行判断，直接导致超时
• 次要性能损耗：每次窗口匹配都需要遍历长度为26的数组做比对，在s长度极大的测试用例下会产生不必要的时间开销

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[] countS = new int[26];
        int[] countP = new int[26];
        // 初始化p的字符计数、s中第一个窗口的字符计数
        for (int i = 0; i < pLen; i++) {
            countP[p.charAt(i) - 'a']++;
            countS[s.charAt(i) - 'a']++;
        }
        // 统计两个计数数组中值相等的字符数，等于26时说明完全匹配
        int match = 0;
        for (int i = 0; i < 26; i++) {
            if (countS[i] == countP[i]) {
                match++;
            }
        }
        if (match == 26) {
            res.add(0);
        }
        // 固定长度窗口向右滑动
        for (int left = 1; left <= sLen - pLen; left++) {
            int right = left + pLen - 1;
            // 处理右边界新进入窗口的字符
            int addCharIdx = s.charAt(right) - 'a';
            countS[addCharIdx]++;
            if (countS[addCharIdx] == countP[addCharIdx]) {
                match++;
            } else if (countS[addCharIdx] - 1 == countP[addCharIdx]) {
                match--;
            }
            // 处理左边界移出窗口的字符
            int removeCharIdx = s.charAt(left - 1) - 'a';
            countS[removeCharIdx]--;
            if (countS[removeCharIdx] == countP[removeCharIdx]) {
                match++;
            } else if (countS[removeCharIdx] + 1 == countP[removeCharIdx]) {
                match--;
            }
            // 匹配直接记录结果
            if (match == 26) {
                res.add(left);
            }
        }
        return res;
    }
}

• 修复窗口移动逻辑：固定长度滑动窗口不管当前是否匹配，每次判断完成后都要同步移动左右边界，移出左边界字符的计数，从根源上避免死循环
• 新增match计数变量：不再每次滑动后遍历整个数组比对，只在字符进出窗口时更新匹配计数，把单次判断的时间复杂度从O(26)降到O(1)，整体时间复杂度稳定为O(n)，可以轻松通过最长字符串的测试用例
• 提前初始化首个窗口，减少循环内重复的边界判断，去掉冗余分支

内容的提问来源于stack exchange，提问作者user19211186