第一题
30. 串联所有单词的子串
上题题意如下：
将w数组里面的字符串随机排列，只要在s字符串中找到相对应的w组成的字符串，则返回s中对应字符串首位元素的第一个下标；
有上述题意所知，解题思路如上一题故事，本题采用hash表和滑动窗口的模型；
首先对于words字符串数组进行处理：
由于这里面的字符串的长度一样，所以我们将每一个字符串一组放在hash1表中，并记录其存放的个数；
其次就是对s字符串的处理分析：
如下图所示：
由于我们存放在hash1中的字符串的长度是len，所以我们在开始左右指针进行移动时，从s的第一个位置和第二个位置开始移动时，结果是不一样的；所以我们分别要从其实位置为0->len-1，分别开始移动左右指针；
且接下来分析右指针所移动的随后判断结束点，如下图所示，
最理想的结果莫过于移动到上图n处，但是也可能移动到m和a处，所以最后的right指针应该移动范围是right+len < n;
关于分析综上所述：
解题步骤如下：
步骤一：
使用hash表来存放words和s里面的字符串；
步骤二：
左右指针移动，移动的长度是words里面字符串的长度；
步骤三：
滑动窗口执行的次数，即外循环，len次；
代码如下所示：
class Solution
{
public List<Integer> findSubstring(String s, String[] words)
{
List<Integer> ret = new ArrayList<Integer>();
// 保存字典中所有单词的频次
Map<String, Integer> hash1 = new HashMap<String, Integer>();
for(String str : words) hash1.put(str, hash1.getOrDefault(str, 0) + 1);
int len = words[0].length(), m = words.length;
for(int i = 0; i < len; i++) // 执⾏次数
{
// 保存窗⼝内所有单词的频次
Map<String, Integer> hash2 = new HashMap<String, Integer>();
for(int left = i, right = i, count = 0; right + len <= s.length();
right += len)
{
// 进窗⼝ + 维护 count
String in = s.substring(right, right + len);
hash2.put(in, hash2.getOrDefault(in, 0) + 1);
if(hash2.get(in) <= hash1.getOrDefault(in, 0)) count++;
// 判断
if(right - left + 1 > len * m)
{
// 出窗⼝ + 维护 count
String out = s.substring(left, left + len);
if(hash2.get(out) <= hash1.getOrDefault(out, 0)) count--;
hash2.put(out, hash2.get(out) - 1);
left += len;
}
// 更新结果
if(count == m) ret.add(left);
}
}
return ret;
}
}第二题
题目如上图所示：
本题我们采用滑动窗口和hash表的解题方法：
步骤一：
将t字符串里面的字符放在hash2表中，使用hash2记录每一个元素出现的次数，并使用kinds变量来记录t字符串中字符的种类；
同时定义左右指针；
步骤二：
进窗口：
右指针移动一位，将所指的字符存于hash1表中，并记录当前所指元素出现在hash表中的次数；同时使用count来记录hash1表中的有效种类；（使用两个hash中同一个元素存放的次数相同时，我们就判定该元素满足t字符串中的种类饱和，故此count++）
步骤三：判断：
当有效种类count==kinds时，记录当前左指针的位置为满足条件字符串的首位置，同时记录当前窗口的长度，最后进行出窗口操作；
左指针所指的元素的两个hash值相同时，count--，同时该元素的hash值-1，左指针左移；
步骤四：
返回数值；
代码如下所示：
class Solution { public String minWindow(String s, String t) { char[] s1 = s.toCharArray(); char[] t1 = t.toCharArray(); int[] hash2 = new int[128]; int kinds = 0;//表示t中元素的种类 for(char ch: t1){ if(hash2[ch] == 0){ kinds++; } hash2[ch] ++; } int[] hash1 = new int[128]; int minLen = Integer.MAX_VALUE,begin = -1; for(int left = 0,right = 0,count = 0;right < s1.length;right++){ char in = s1[right]; hash1[in]++; if(hash2[in] == hash1[in]){ count++ ; } while(kinds == count){ if(right-left+1 < minLen){ begin = left; minLen = right-left+1; } char out = s1[left++]; if(hash2[out] == hash1[out]){ count--; } hash1[out]--; } }if(begin == -1){ return new String(); }else{ return s.substring(begin,begin+minLen); } } }
ps：本次的内容就到这里了，如果大家感兴趣的话就请一键三连哦！！！
