题目1

  1. 给定长度为m的字符串aim，以及一个长度为n的字符串str，
  2.  问能否在str中找到一个长度为m的连续子串，使得这个子串刚好由aim的m个
  3.  字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1
  2.   /*
  4.    */
  5.   public static int slidingWindow1(String aim, String str){
  6.     if(str.length()<=0 || aim.length()<=0 || str.length()<aim.length()){
  7.       return -1;
  8.     }
  9.     char[] aimChars = aim.toCharArray();
  10.     //定义一个欠债表
  11.     int[] count = new int[256];
  12.     for (int i = 0; i <aimChars.length; i++) {
  13.       count[aimChars[i]]++;
  14.     }
  15.     System.out.println(Arrays.toString(count));
  17.     int R = 0;
  18.     int invalid = 0;
  19.     char[] strChars = str.toCharArray();
  20.     //定义一个窗口，大小为aim.length
  21.     int M = aimChars.length;
  22.     //先让窗口有M个字符
  23.     for (; R <M; R++){
  24.       if(count[strChars[R]]--<=0){
  25.         invalid++;
  26.       }
  27.     }
  28.     //滑完第一个窗口，先判断是否存在同源异构词
  30.     //第一次形成长度为M的窗口，继续往后滑
  31.     for (;R<str.length();R++){
  32.       if(invalid == 0){
  33.         return R-M;
  34.       }
  35.       if(count[strChars[R]]-- <=0){
  36.         invalid++;
  37.       }
  39.       //把窗口外的字符去除，再次欠债
  40.       if(count[strChars[R-M]]++ <0){
  41.         invalid--;
  42.       }
  44.     }
  45.     return invalid==0?R-M: -1;
  47.     }
  49.   public static void main(String[] args) {
  50.     String aim = "abcd";
  51.     String str = "ifadkfgabdc";
  52.     System.out.println(slidingWindow1(aim, str));
  53.   }