题解 | #找到字符串中的异位词#

import java.util.*;

/**
 * NC387 找到字符串中的异位词
 * @author d3y1
 */
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param s string字符串
     * @param p string字符串
     * @return int整型一维数组
     */
    public ArrayList findWord (String s, String p) {
        // return solution1(s, p);
        return solution2(s, p);
    }

    /**
     * 滑动窗口
     * @param s
     * @param p
     * @return
     */
    private ArrayList solution1(String s, String p){
        ArrayList<Integer> list = new ArrayList<>();
        char[] pArr = p.toCharArray();
        Arrays.sort(pArr);
        String pStr = String.valueOf(pArr);

        int len = s.length();
        int gap = pArr.length;
        char[] subArr;
        String subStr;
        for(int i=0; i+gap<=len; i++){
            subArr = s.substring(i, i+gap).toCharArray();
            Arrays.sort(subArr);
            subStr = String.valueOf(subArr);
            // 匹配
            if(subStr.equals(pStr)){
                list.add(i);
            }
        }

        return list;
    }

    /**
     * 双指针
     * @param s
     * @param p
     * @return
     */
    private ArrayList solution2(String s, String p){
        ArrayList<Integer> list = new ArrayList<>();

        // 字符串s 统计字符个数
        int[] sCount = new int[26];
        // 字符串p 统计字符个数
        int[] pCount = new int[26];
        for(char ch: p.toCharArray()){
            pCount[ch-'a']++;
        }

        // 双指针
        for(int left=0,right=0; right<s.length(); right++){
            sCount[s.charAt(right)-'a']++;
            while(sCount[s.charAt(right)-'a'] > pCount[s.charAt(right)-'a']){
                sCount[s.charAt(left)-'a']--;
                left++;
            }
            if(right-left+1 == p.length()){
                list.add(left);
            }
        }

        return list;
    }
}