题目：

  1. 给定一个字符串 s 和一些长度相同的单词 words。找出 s 中恰好可以由 words 中
  2. 所有单词串联形成的子串的起始位置。
  4. 注意子串要与 words 中的单词完全匹配，中间不能有其他字符，
  5. 但不需要考虑 words 中单词串联的顺序。
  7. 示例 1：
  9. 输入：
  10. s = "barfoothefoobarman",
  11. words = ["foo","bar"]
  12. 输出：[0,9]
  13. 解释：
  14. 从索引 0 和 9 开始的子串分别是 "barfoo" 和 "foobar" 。
  15. 输出的顺序不重要, [9,0] 也是有效答案。
  16. 示例 2：
  18. 输入：
  19. s = "wordgoodgoodgoodbestword",
  20. words = ["word","good","best","word"]
  21. 输出：[]
  23. 来源：力扣（LeetCode）
  24. 链接：https://leetcode-cn.com/problems/substring-with-concatenation-of-all-words
  25. 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

答案：

时间：

双指针不愧是我最菜的算法，看不出来不说，知道了双指针，还经常写错。

  1. class Solution:
  2.     def findSubstring(self, s: str, words: List[str]) -> List[int]:
  3.         if not s:return []
  4.         if not words:return []
  5.         n,k,m=len(words),len(words[0]),len(s)
  6.         ans=[]
  8.         for p in range(k):
  9.             record= collections.Counter(words)
  10.             i,j=p,p+k
  11.             while j<=m:     
  12.                 now_word=s[j-k:j]
  13.                 # print(i,j,record,now_word)
  14.                 if now_word not in record:
  15.                     i=j
  16.                     j=i+k
  17.                     record= collections.Counter(words)
  18.                 else:
  19.                     if record[now_word]>0 and j-i==n*k:
  20.                         ans.append(i)
  21.                         i+=k
  22.                         record[s[i-k:i]]+=1
  23.                     while record[now_word]<=0:
  24.                         i+=k
  25.                         record[s[i-k:i]]+=1
  26.                     j+=k
  27.                     record[now_word]-=1              
  28.         return ans

要点：

1. 对0-K分别做一次双指针

每个循环间要重置Counter

2. 如果这个单词没找到

i移到j后面，重置Counter

3. 如果这个单词还有，并且长度差满足了nk

答案入i，ij后移，并且不会经过while循环，当前单词减1，因为i右移，所以前面单词+1

4. 如果这个单词没有了，不断右移i，直到找回来（一定能找到）

i 右移有限次，前缀单词有限次+1，找回单词后，j右移，当前单词-1。

其他：

代码报错：总感觉自己做复杂了