文章目录
- 1、长度最小的子数组
- 2、无重复字符的最长子串
- 3、最大连续1的个数 Ⅲ
- 4、将x减到0的最小操作数
- 5、水果成篮
- 6、找到字符串中所有字母异位词
- 7、串联所有单词的子串
- 8、最小覆盖子串
通常，算法的主体说明会放在第一道题中。但实际上，不通常。
算法在代码上的体现不是一道题能全部看出来的。
1、长度最小的子数组
链接
窗口其实就是指一块区间，用一些条件限制住的一个区间，比如数组某两个位置之间就是一个窗口。
暴力解法就是找到所有子数组，找到最小长度。那么优化一下，定义两个变量ab，ab都指向数组第一个元素，然后加上此时的数，b往后走一步，a固定住。也就是说a固定一个数，b在之后的所有数中找达到条件的连续子数组。b每走一步，就加上当前的值。满足条件时，b就可以不动了，此时b停在最后一个相加的数。由于都是正整数，b往后继续走也肯定会满足条件，而题目要求找最小长度，所以就没必要继续走了。此时以a代表的值为开头的连续数组就找到了，计算它的长度，保存下来。
a往后走一步，此时b可以继续不动，因为相对于上一个连续数组，我们已经计算了和的值，那么减去开头的值就是现在ab所限制的区间的总和，如果不符合条件，b就继续往后走。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, len = INT_MAX;
int l = 0, r = 0;
while(r < n)
{
sum += nums[r];
while(sum >= target)
{
len = min(len, r - l + 1);
sum -= nums[l];
++l;
}
++r;
}
return len == INT_MAX ? 0 : len;
}
};
2、无重复字符的最长子串
链接
暴力解法就是找到所有的子串，得到最大值，当然遇到有重复的就不能继续了。如何找重复，如果是Python，可以用in来判断，不过C++就用哈希就好，每次开始一个子串的逐个判断时，就创建一个哈希表，把每个字符都放进去，这样有重复的就可以判断出来了。
优化暴力解法。当遇到重复时，就从下一个字符又开始计算，但有可能重复的字符在原本的子串的第4个位置，那么不如找到原子串中重复字符的位置，从这个位置的下一个位置开始再继续判断子串，这样就减少了一些步骤。
当窗口内有重复字符时再出窗口，找到重复字符在原子串位置的下一个位置；判断重复用哈希表。
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = {0};
int n = s.size(), len = 0;
int r = 0, l = 0;
while(r < n)
{
hash[s[r]]++;
while(hash[s[r]] > 1) //有重复了, 该出窗口
hash[s[l++]]--;
len = max(len, r - l + 1);
r++;
}
return len;
}
};
3、最大连续1的个数 Ⅲ
链接
暴力解法很简单，就是依次枚举即可。
优化暴力解法。滑动窗口的主要思路就是如何进窗口和出窗口。如果遇到1就可以继续往后走，遇到0就用一个计数器，让计数器加1，直到大于k时就出窗口。下一次进窗口时，起始位置就得变更。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int l = 0, r = 0, zero = 0, ret = 0;
while(r < n)
{
if(nums[r] == 0) zero++;
while(zero > k)
if(nums[l++] == 0) zero--; //不仅出窗口, 也同时让l往后走以及把zero归0
ret = max(ret, r - l + 1);
r++;
}
return ret;
}
};
4、将x减到0的最小操作数
链接
如果按照题目给的定义去做，会发现要如何选择被删的数比较麻烦。不如换个思路，抛开左或右边的数不谈，如果要符合要求，那么去除左或右边的数，剩下的数就应当等于sum - x。所以现在的思路就是找到一个最长的子数组，所以它肯定连续，让其总和等于sum - x。
让sum - x = target。先从头开始，依次加上每个值，直到加上某个值后正好 >= target，也就是没加之前总和是小于target的，这时候指向区间右端的指针right就不需要动了，因为根据提示，每个数都大于0，所以再往后走就肯定是大于target了。到达这个位置，指向区间左端的指针left就应该往后走。这时候right不需要动，因为right之前的区间肯定小于target，而left后移一步，就更小了，或许这时候left和right规定的区间的数的总和就等于target了。
那么进窗口就是让right往后走，并且加上当前的值；出窗口就是在区间总和大于target时，就出，不判断等于是因为我们要求最终要等于，如果等于也要跳，就控不住了；当总和等于target时就更新结果。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int n = nums.size();
int l = 0, r = 0, tmp = 0, res = -1;
int sum = 0;
for (int e : nums) sum += e;
int target = sum - x;
if(target < 0) return -1; //先总体判断一下
while(r < n)
{
tmp += nums[r];
while(tmp > target)
tmp -= nums[l++];
if(tmp == target)
res = max(res, r - l + 1);
r++;
}
if(res == -1) return res;
else return n - res;
}
};
5、水果成篮
链接
仔细看题就能明白题意。本质上就是找出一个最长的子数组，数组中的数不超过2种。
暴力解法中要控制种类数量不超过2，可以建立哈希表，当第3种进入哈希表时就停止操作。
优化暴力解法。当遇到第3种出现时，也就是right指针指向第3种类型时，就停止，然后left往后移一步，移到left和right之间的区间只有两种数时才停止，然后接着right再继续往后走，去检查是否有第3种类型出现。
代码中做了一些优化。k表示种类。
class Solution {
public:
int totalFruit(vector<int>& f) {
int hash[100001] = {0};
int n = f.size();
int l = 0, r = 0, res = 0;
int k = 0;
while(r < n)
{
if(hash[f[r]] == 0) ++k;
++hash[f[r]];
while(k > 2)
{
--hash[f[l]];
if(hash[f[l]] == 0) --k;
++l;
}
res = max(res, r - l + 1);
++r;
}
return res;
}
};
6、找到字符串中所有字母异位词
链接
此题往后的三道题一脉相承。
对于如何判断异位词，我们可以用两个哈希表，只要相同的字符出现的次数相同即可，只要有一个不同就不行。按照暴力解法，根据p字符串的长度，从s的开头开始找，每次都找p长度个，然后比较；接着从下一个字符开始再找并比较。
优化暴力解法。按照暴力解法，比如cbae，如果要3个字符，就能有两个选择，cba，bae。两者只有一个字符的不同，所以不如在更换区间时，指向区间左右端的left和right指针都往后走一步即可，不需要让right从left下一个字符处再去判断。另一个角度理解就是，比如p长度是3，当right走到了第四个字符时，让left往后移一步，这样就是下一个3个字符区间。
对于哈希表判断，可以建一个26大小的哈希表，但应当优化一下，利用变量count来统计窗口中有效字符的个数。s和p对比，可能出现p中c字符出现1次，但是s中某个区间c字符出现2次。剩下的看代码。
class Solution {
public:
vector<int> findAnagrams(string s, string p)
{
vector<int> res;
int hash1[26] = {0};
for(auto ch : p) hash1[ch - 'a']++;
int hash2[26]{0};
int m = p.size();
int l = 0, r = 0, n = s.size(), count = 0;
while(r < n)
{
char in = s[r];
if(++hash2[in - 'a'] <= hash1[in - 'a']) ++count;
if(r - l + 1 > m)
{
char out = s[l++];
if(hash2[out - 'a']-- <= hash1[out - 'a']) --count;
}
//在r和l之间的区间有3个数时, 如果符合要求就会push进去, 此时count=m
//当更换一个区间后, 更换之前count就已经计入了第m + 1个数, 所以这里当去掉一个数后也可以判断
if(count == m) res.push_back(l);
++r;
}
return res;
}
};
7、串联所有单词的子串
链接
此题和前后两道一脉相承。
和上一题相似，把异位词改成单词就行。但还有点不一样。上一题是滑动窗口 + 哈希表，这里也是。这道题中，移动的步长应当和words中字符串长度相同，不过从一个单词的每一个字符处开始滑动窗口，进行多次；哈希表是<string, int>。
直接看代码。
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words)
{
vector<int> res;
unordered_map<string, int> hash1;
for(auto& e: words) hash1[e]++;
int len = words[0].size(), m = words.size();
for(int i = 0; i < len; ++i)
{
unordered_map<string, int> hash2;
for(int l = i, r = i, count = 0; r + len <= s.size(); r += len)
{
string in = s.substr(r, len);
hash2[in]++;
if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
if(r - l + 1 > len * m)
{
string out = s.substr(l, len);
if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
l += len;
}
if(count == m) res.push_back(l);
}
}
return res;
}
};
8、最小覆盖子串
链接
此题和前面两道一脉相承。
暴力解法就是挨个字符作为开头去判断。并且从上面的那些题来看，判断是否包含用哈希表就好。哈希表中要求的那些字符的对应的数字大于等于t中的才行，所以s和t各有一个哈希表。
当一个区间符合要求后，指向区间左端的指针left向后移一步，指向右端的指针right先不动，判断现在的这个区间是否符合要求，如果不符合right再往后走继续判断。
所以进窗口就是让s的字符在哈希表中的数值增加，hash2[in]++；要出窗口前，判断是否符合要求，要出就hash2[out]–。in是right指向，out是left指向的。在出之前，判断之后，更新结果。
优化一下，也是之前题的思路，用一个变量count来标记有效字符的种类。进窗口时，hash2[in] 等于hash1[in]，count就++；出窗口之前，hash2[out] 等于 hash1[out]时，count就–。判断条件就是count是否等于hash1.size()。count为什么要这样更改？仔细想想s对应的hash1中某个字符出现的次数多的话如何应对？
看代码
class Solution {
public:
string minWindow(string s, string t)
{
int hash1[128] = {0};
int k = 0; //统计t中的有效字符
for(auto ch : t)
if(hash1[ch]++ == 0) ++k;
int hash2[128] = {0};
int min = INT_MAX, begin = -1;
for(int l = 0, r = 0, count = 0; r < s.size(); ++r)
{
char in = s[r];
if(++hash2[in] == hash1[in]) ++count;
while(count == k) //开始判断
{
if(r - l + 1 < min)
{
min = r - l + 1;
begin = l;
}
char out = s[l++];
if(hash2[out]-- == hash1[out]) --count;
}
}
if(begin == -1) return "";
else return s.substr(begin, min);
}
};
结束。
