LeetCode面试题Day12|LC209 长度最小的子数组、LC30 串联所有单词的子串

题目一：

指路：

. - 力扣（LeetCode）209 长度最小的子数组

思路与分析：

滑动窗口，目的在于降低算法的时间复杂度，每次只维护一定长度的数组而非原数组的全部元素。那么既然需要长度，就需要用到起止位置。我们将i和j定义为维护的起止位置，二者都初始化为数组首位置。那么需要维护的长度是多少我们暂时不得而知，只知道维护到的元素和大于等于给定的目标值target。那么起始位置不变，将终止位置后移，如果得到的元素和满足条件那么此时维护到的数组元素即为一组满足条件的元素，此时也能得到这组元素的长度，是为j-i+1。同理，将首位置后移或许也能找到一组符合条件的元素，那么此时需要求的就是两种情况的较小值。需要注意的是：当首位置后移时，映射在数组中就是减去首元素对应的元素值，也就是nums[i]。那么还有一种情况，就是原数组全部的元素和都小于target，那么这时候就不会进入while循环，自然在前面定义的最终子串长度还是INT_MAX，那么我们使用一个三目运算符，目的是让最终结果值在初始值不改变的情况下赋值为0，否则返回我们求的的ans。

代码：

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int n = nums.size();int i = 0, j = 0;  // 记录起止位置int sum = 0;  // 每轮求得的和int sublen = 0;  // 每轮的子串长度int ans = INT_MAX;  // 最后的子串长度for (j; j < n; j++) {sum += nums[j];  // 开始动态求和while (sum >= target) {  // 当求到的和>=target时求更小的数组长度sublen = j - i + 1;  // 当前轮的子串长度ans = min (ans, sublen);  // 求更小的子串长度sum -= nums[i];  // 因为要将起始位置和终止位置后移所以要减去起始位置的元素值i++;  // 起始位置后移}}return ans == INT_MAX ? 0 : ans;}
};

题目二：

指路：

. - 力扣（LeetCode）30 串联所有单词的子串

思路与分析：

划分单词，单词的数量为comn个，每个单词的长度为m，现在共有n个长度的字符串供我们在其中寻找串联子串。用一个哈希表diff表示窗口中单词出现的次数与words数组中单词出现次数的差。在窗口中出现该单词的数值+1，在words中出现该单词的数值-1。将窗口右移，右侧新增一个单词，左侧摒弃一个单词。同时更新diff数组值。如果得到符合条件的数组值则把该轮的初始位置start放入结果数组ans。

代码：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {int comn = words.size();  // 需要匹配的是comn个字符串，小的值int m = words[0].size();int n = s.length();  // s中一共有n长度的字符，大的值vector<int> ans;  // 结果数组for (int i = 0; i < m && i + comn * m <= n; ++i) {// 外层起始位置unordered_map<string, int> diff;  // 统计当前窗口单词出现的次数for (int j = 0; j < comn; ++j) {++diff[s.substr(i + j * m, m)];  // 将子串加入diff并计数}for (string &word : words) {// 在给出的words数组内排查单词对比其在diff数组中出现的次数if (--diff[word] == 0) {  // 次数减到0删除单词diff.erase(word);}}for (int start = i; start < n - comn * m + 1; start += m) {// 内层起始位置if (start != i) {string word = s.substr(start + (comn - 1) * m, m);  // 添加新单词if (++diff[word] == 0) {diff.erase(word);}word = s.substr(start - m, m);if (--diff[word] == 0) {diff.erase(word);  // 移除已移出的单词}}if (diff.empty()) {  // 符合条件，将起始位置放入结果数组ans.emplace_back(start);}}}return ans;}
};