题目

分析

两种解法。
都使用到了hash的知识。对于第一种解法，我们比较直接的循环得到所有可能的结果，也就是和单词数组长度和相同的所有子串，从i=0开始，一直到最后，对于每一个循环得到的子串就进行判断即可，判断就是通过比较两个哈希是否相同。

 for(int i=0;i<S.length()-all_len+1;i++)
        {
            String temp_str=S.substring(i,i+all_len);//每一次循环得到的和单词数组长度相同的子串
            //System.out.println(temp_str);
            HashMap<String,Integer> temp_map=new HashMap<>();
            for(int j=0;j<temp_str.length()-one_word+1;j+=one_word)//然后对这个字符串一个单词一个单词的进行拆分
            {
                String temp_temp_str=temp_str.substring(j,j+one_word);
                temp_map.put(temp_temp_str,temp_map.getOrDefault(temp_temp_str,0)+1);
            }
　　   //然后进行比较，相同的话，就是符合条件的　　
            if(map.equals(temp_map))
            {
                System.out.println(i);
                res.add(i);
            }
        }

然后就是解法2了，对于解法2我们使用到了滑动窗口的概念，当然也是通过比较hash来解题的，看一下核心的代码

for(int i=0;i<oneWord;i++)
        {
           int left=i;
           int right=i;
           int count=0;
           HashMap<String,Integer> tempMap=new HashMap<>();
           while(right+oneWord<=wordLength)
           {
               String tempStr=S.substring(right,right+oneWord);
               tempMap.put(tempStr,tempMap.getOrDefault(tempStr,0)+1);
               count++;
               right+=oneWord;
               //一个判断条件实则是对两种情况的判断
               //case1　如果加入的tempStr是字符数组中没有出现过的话,
               // 我们就要一直从左边出队,直到这个不符合条件的出了队,也就是将整个队列中的字符全部出队
               //case2　如果是数量过多的话,我们能做的也只是从左边一直出队
               //两种情况一中策略
               while(tempMap.getOrDefault(tempStr,0)>map.getOrDefault(tempStr,0))
               {
                   String temptempStr=S.substring(left,left+oneWord);
                   tempMap.put(temptempStr,tempMap.getOrDefault(temptempStr,0)-1);
                   count--;
                   left-=oneWord;
               }
               if(count==wordLength) res.add(left);
           }
        }

第一个问题，最外层的for循环

for(int i=0;i<oneWord;i++)

我们分了三个路径，分别是如下

从i=0开始，每次走单个单词的长度
从i=1开始，每次走单个单词的长度
从i=2开始，每次走单个单词的长度

这样和从i=0开始，每次走一个覆盖的是相同的。
然后就是滑动窗口的进和出

    //最开始left和right都是起始位置
    while(right+oneWord<=wordLength)
           {   
               //每次循环都将一个单词长度的加入到队列中
               String tempStr=S.substring(right,right+oneWord);
               tempMap.put(tempStr,tempMap.getOrDefault(tempStr,0)+1);
               count++;
               right+=oneWord;

上面的代码就是进入窗口的代码

               //一个判断条件实则是对两种情况的判断
               //case1　如果加入的tempStr是字符数组中没有出现过的话,
               // 我们就要一直从左边出队,直到这个不符合条件的出了队,也就是将整个队列中的字符全部出队
               //case2　如果是数量过多的话,我们能做的也只是从左边一直出队
               //两种情况一中策略
               while(tempMap.getOrDefault(tempStr,0)>map.getOrDefault(tempStr,0))
               {

对于循环条件，注解已经给出了很详细的解释了，但是对于没有进入的情况，表面现在的temp哈希是符合条件的，只需要再满足count的数量就是一个解了

                   String temptempStr=S.substring(left,left+oneWord);
                   tempMap.put(temptempStr,tempMap.getOrDefault(temptempStr,0)-1);
                   count--;
                   left-=oneWord;
               }
               if(count==wordLength) res.add(left);
           }

代码展示

解法1:

public static ArrayList<Integer> findSubstring(String S, String[] L)
    {
        ArrayList<Integer> res=new ArrayList<>();
        int one_word=L[0].length();
        int word_length=L.length;
        int all_len=one_word*word_length;
        HashMap<String,Integer> map=new HashMap<>();
        //init
        for(int i=0;i<L.length;i++)
        {
            map.put(L[i],map.getOrDefault(L[i],0)+1);
        }
        //do
        for(int i=0;i<S.length()-all_len+1;i++)
        {
            String temp_str=S.substring(i,i+all_len);
            //System.out.println(temp_str);
            HashMap<String,Integer> temp_map=new HashMap<>();
            for(int j=0;j<temp_str.length()-one_word+1;j+=one_word)
            {
                String temp_temp_str=temp_str.substring(j,j+one_word);
                temp_map.put(temp_temp_str,temp_map.getOrDefault(temp_temp_str,0)+1);
            }
            if(map.equals(temp_map))
            {
                System.out.println(i);
                res.add(i);
            }
        }
        return res;
    }

解法2:

  public ArrayList<Integer> findSubstring(String S, String[] L){
        ArrayList<Integer> res=new ArrayList<>();
        HashMap<String,Integer> map=new HashMap<>();
        int oneWord=L[0].length();
        int wordLength=L.length;
        int allLen=oneWord*wordLength;
        //init
        for(int i=0;i<L.length;i++)
        {
            map.put(L[i],map.getOrDefault(L[i],0)+1);
        }
        //三种开始的位置
        for(int i=0;i<oneWord;i++)
        {
           int left=i;
           int right=i;
           int count=0;
           HashMap<String,Integer> tempMap=new HashMap<>();
           while(right+oneWord<=S.length())
           {
               String tempStr=S.substring(right,right+oneWord);
               tempMap.put(tempStr,tempMap.getOrDefault(tempStr,0)+1);
               count++;
               right+=oneWord;
               //一个判断条件实则是对两种情况的判断
               //case1　如果加入的tempStr是字符数组中没有出现过的话,
               // 我们就要一直从左边出队,直到这个不符合条件的出了队,也就是将整个队列中的字符全部出队
               //case2　如果是数量过多的话,我们能做的也只是从左边一直出队
               //两种情况一中策略
               while(tempMap.getOrDefault(tempStr,0)>map.getOrDefault(tempStr,0))
               {
                   String temptempStr=S.substring(left,left+oneWord);
                   tempMap.put(temptempStr,tempMap.getOrDefault(temptempStr,0)-1);
                   count--;
                   left+=oneWord;
               }
               if(count==wordLength) res.add(left);
           }
        }
         Collections.sort(res);
        return res;
    }

学习情况

实现两种解法，一次，很重要的一道题。