网站备案是否关闭/厦门关键词优化平台

package com.areio.suanfa.zifuchuan;/*寻找所有字母异位词
* 给定一个字符串S和一个非空字符串T，找到S中所有是T的 字母异位词 的子串,并返回这些子串的起始索引
*
* "cba"是"abc"的异位词
* 这意味着题目要求在S中找到所有是T的全排列的子串
* S="cba eba bac d",T="abc"  返回0和6
*
* */import java.util.ArrayList;
import java.util.HashMap;
import java.util.Map;/*
* s是给定的字符串
* t是目标字符串
*
* 快慢指针在数组上的应用
* */
/*注意:
*1、在扩大和缩小窗口的时候要维护valid
*2、在缩小窗口的时候要更新最终结果
*
* */
public  class FindAnagrams {public static int[] findAnagrams(String s,String t){//两个字符计数器，分布统计每个字符出现的次数，key是字符，val是出现次数//其中need代表目标字符串每个字符需要出现次数，window统计在当前窗口中出现目标字符串中每个字符的次数Map<Character,Integer> need=new HashMap<>();Map<Character,Integer> window=new HashMap<>();//统计目标字符串中每个字符需要出现的次数，比如t=“abc”，那么need={a=1,b=1,c=1}char[] tArray = t.toCharArray();for (char c: tArray) {//添加或者覆盖某键值对//need.getOrDefault(c,0)代表如果该key存在，则取key对应的值，不存在则得到默认值0need.put(c,need.getOrDefault(c,0)+1);}char[] sArray = s.toCharArray();//设置快慢指针的初始位置，此时窗口[left,right)=[0,0)为空int left=0,right=0;//valid代表满足要求的字符个数，比如need={a=1,b=2} 而window={a=1,b=1}那么只有a达到预期次数，此时valid=1int valid=0;//res用于存放结果，即满足条件的子串的起始索引ArrayList<Integer> res=new ArrayList<>();//int[] res=new int[s.length()];//标记字符串存到第几个索引//int index=0;while(right<s.length()){//将要加入到窗口的字符char c=sArray[right];//扩大窗口right++;//更新窗口内的数据if (need.containsKey(c)){//如果need需要这个key，就在统计窗口中出现该字符的次数window.put(c,window.getOrDefault(c,0)+1);//如果窗口中出现该字符的次数等于目标子串中需要这个字符的次数if(window.get(c)==need.get(c)){valid++;}}//是否要开始缩小窗口；条件是只要窗口的大小（左闭右开）等于目标字符串的长度，那么就开始收缩,一旦窗口大小小于目标字符串长度就停止收缩while ((right-left)==t.length()){//长度相等之外，还需满足窗口中出现每个字符串的个数是否与目标字符串每个字符所需出现的次数一致if (valid==need.size()){//res[index]=left;//index++;res.add(left);}//将要被踢出窗口的字符char d=sArray[left];left++;//更新窗口内的数据if (need.containsKey(d)){//如果need需要这个key,且恰好这个字符在窗口中出现的次数等于它需要出现的次数,那么缩小完 这个字符出现的次数-1，必然满足条件的字符就会-1if (window.get(d)==need.get(d)){valid--;}window.put(d,window.getOrDefault(d,0)-1);}}//重复扩大窗口和缩小窗口的过程}//return res;int[] result = new int[res.size()] ;for(int i=0;i<res.size();i++){result[i]=res.get(i);}return result;}public static void main(String[] args) {int[] anagrams = findAnagrams("cbacebabacd", "abc");for (int i:anagrams) {System.out.println(i);}}}