Leetcode每日一题30. 串联所有单词的子串

链接：30. 串联所有单词的子串

移动窗口，花了很久，AC以后，高歌一首。。。

思路
一眼看上去就是移动窗口，重点在于窗口的初始化以及记录在移动窗口过程中所需单词数目的改变

1. 初始化：
   对于该题一次移动窗口是不够的，由于窗口是按照单词距离移动，所以需要从开始单词的每一个字符都初始化一个窗口，共初始化words[0].length()个窗口

2. 窗口的移动：
   首先用num记录所需单词的总数，即word.length，在移动的过程中我们不用在意细节，只要一知道被移除的单词是否是所需单词，如果是所需单词并且该单词在窗口中出现的数量小于等于所需该单词的数量就把num++；二知道新来的单词是否是所需单词，如果是并且该单词在窗口中出现的数量小于等于所需该单词的数量，就把num–。每次移入一个所需单词看num是否为0即可

class Solution {
    
    public List<Integer> findSubstring(String s, String[] words) {
    
        HashMap<String,Integer> cnt = new HashMap<>();
        List<Integer> ans = new ArrayList<>();
        int w = words[0].length();
        for(int i=0;i<words.length;i++){
    
            cnt.put(words[i],cnt.getOrDefault(words[i], 0) + 1);
        }

        for(int i=0;i<w;i++){
    
            HashMap<String,Integer> m= new HashMap<>();
            int num = words.length;//记录还需要在窗口内的单词数
            m.putAll(cnt);

            int l = i;
            int r = i + w * words.length-1;
            if(r > s.length() - 1)break;//初始的窗口装不下所有单词直接结束
            //滑动窗口初始化
            for(int j=l;j<=r && j+w-1<=r;j+=w){
    
                String cur = s.substring(j,j+w);
                if(!m.containsKey(cur))continue;
                int tmp = m.get(cur);
               m.put(cur,tmp - 1);
                if(tmp - 1 >= 0) {
    
                    num--;
                }
            }
            if(num == 0){
    //测试初始窗口是否满足要求
                ans.add(i);
            }
            //移动滑动窗口
            for (l+=w,r+=w; r<s.length(); l+=w,r+=w){
    
                String old = s.substring(l-w,l);
                String cur = s.substring(r-w+1,r+1);
                //处理移出窗口的单词
                if(m.containsKey(old)){
    
                    int tmp = m.get(old);
                    if(tmp >= 0) {
    
                        num++;
                    }
                    m.put(old,tmp + 1);
                }
                //处理刚进入窗口的单词
                if(!m.containsKey(cur))continue;
                int tmp = m.get(cur);
                m.put(cur,tmp - 1);
                if(tmp - 1 >= 0) {
    
                    num--;
                }
                if(num == 0){
    
                    ans.add(l);
                }
            }

        }
        return ans;
    }
}

• 时间复杂度（N*M）N为单词长度，M为字符串长度
• 空间复杂度（N）哈希表