文章目录
- 例题1：长度最小的子数组
- 例题2：无重复字符的最长子串
- 例题3：最大连续1的个数 III
- 例题4：将 x 减到 0 的最小操作数
- 例题5：水果成篮
- 例题6：找到字符串中所有字母异位词
- 例题7：串联所有单词的子串
- 例题8：最小覆盖子串
例题1：长度最小的子数组
长度最小的子数组
分析：
若暴力枚举，用三重循环列出所有可能：
int n = nums.size();
for(int i = 0; i < n; i++){//以i位置开头的所有子数组
for(int j = i; j < n; j++){//以j位置为结尾
int n = 0;
for(int k = i; k <= j; k++){//依次算出各个子数组的和，然后比较和大于等于target的子数组的长度那个最小
n += nums[k];
………………………………………………………………
//时间复杂度 O(N^3)
简单的优化：计算子数组和时不需要每次都从头开始
int n = nums.size();
for(int i = 0; i < n; i++){//以i位置开头的所有子数组
int n = 0;
for(int j = i; j < n; j++){
n += nums[j];
//时间复杂度 O(N^2)
因为这道题说数组中的数全为正整数，所以 += 操作后 n 肯定是递增的（单调性） —— 当 n >= target 时就没有继续 += 的必要了，此时 n 就是这个循环中 长度最小的、和大于等于target的子数组的和
以 2 3 1 2 4 3（target = 7） 为例，第一层循环过后，我们知道了以0位置开头的子数组中，2 3 1 2 是我们想要的；第二次循环会从3开始，我们需要再从头开始枚举子数组吗 —— 我们可以记录第一次循环结束位置，然后直接以3 1 2为基础继续
● 根据以上的分析，我们改用两个指针（同向双指针（同向指两个指针都不回退，向着一个方向移动））来实现上述的操作：
left 和 right 两个“指针”之间形成一个区间，并记录（维护）着这个区间内的信息（子数组和、长度），两个指针从左向右移动的过程中，这个区间就像一个窗口一样在数组中滑动 —— 滑动窗口
以上的思路为：利用单调性，使用“同向双指针（滑动窗口）”优化问题
● 怎么用：
1.left = 0，right = 0
2.进窗口
3.判断 <-> 出窗口
● 这个方法的正确性：
利用单调性，规避了很多没有必要的枚举行为
在暴力解法中若发现了单调性，可以考虑用这个方法
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size(), sum = 0, len = INT_MAX;//结果
for(itn left = 0, right = 0; right < n; right++){
sum += nums[right];//进窗口（新进入left和right之间的数据，会产生什么影响--sum+=nums[right]）
while(sum >= target)//判断
{
len = min(len, right - left + 1);//更新结果 -- 可能在判断后，也可能在出窗口后（因题而异）
sum -= num[left++];//出窗口（left++过后，左侧数据不再处于left和right之间）
}
}
return len;
}
};
● 时间复杂度：
我们的每一步操作都让 left / right 向右移动，直至最后 -> O(N)
例题2：无重复字符的最长子串
无重复字符的最长子串
暴力解法：暴力枚举（从左往右依次枚举以左侧数字为开头的满足要求的所有子串）-- 判断满足要求：可以用哈希表储存已遍历子串部分的字符，依次判断字符是否重复
模拟：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int hash[128] = {0};//使用数组模拟哈希表，0表示没有，1出现一次，2出现两次
int len = 0;
for(int left = 0, right = 0; right < s.size(); right++){
hash[s[right]]++;//进窗口
while(hash[s[right]] > 1)//判断
hash[s[left++]]--;//出窗口
len = max(len, right - left + 1);//更新结果
}
return len;
}
};
例题3：最大连续1的个数 III
最大连续1的个数 III
问题转化：找出0的个数不超过k个的最长子数组
暴力求解：从左往右依次以每个数为开头，往后找最长可以到哪 ->O(N^2)
模拟示例1：
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int ret = 0;
for(int left = 0, right = 0, zero = 0; right < nums.size(); right++){//zero记录0的个数
//对于right而言，1进窗口时不用管
if(nums[right] == 0) zero++;//0进窗口
while(zero > k)//判断
if(nums[left++] == 0) zero--;//出窗口
ret = max(ret, right - left + 1);//更新结果
}
return ret;
}
};
例题4：将 x 减到 0 的最小操作数
将 x 减到 0 的最小操作数
分析：
正 难 则 反
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
//题目说了nums[i]>0
int sum_ = 0;
for(auto e : nums) sum_+= e;
int target = sum_ - x;
if(target < 0) return -1;//!
int n = nums.size(), len = -1;
for(int left = 0, right = 0, sum = 0; right < n; right++){
sum += nums[right];//入窗口
while(sum > target){//判断
sum -= nums[left++];//出窗口
}
if(sum == target)
len = max(len,right - left + 1);//更新结果
}
return len == -1 ? -1 : n - len;//如果len初始被赋予 0，这地方用len == 0做判断，遇到 target == 0 的情况会出问题
}
};
例题5：水果成篮
水果成篮
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int n = fruits.size();
int hash[100001] = {0};//数组模拟哈希表，表示各水果类型所持数目
//也可以用unordered_map，似乎更方便些
//题目说 1 <= fruits.length <= 10^5，结果开10010个空间不给过，合着 <= 10^5的意思是数量级不是具体数呗，这个老六
int num = 0, sort = 0;
for(int left = 0, right = 0; right < n; right++){
if(hash[fruits[right]] == 0) sort++;
hash[fruits[right]]++;//入窗口
while(sort > 2){
if((--hash[fruits[left++]]) == 0)//出窗口
sort--;
}
num = max(num, right - left + 1);
}
return num;
}
};
这个方法我和老师写的几乎一模一样 —— 我终于出息了（
老师用哈希表的演示：
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> hash;
int ret = 0;
for(int left = 0, right = 0; right < fruits.size(); right++){
hash[fruits[right]]++;//进窗口
while(hash.size() > 2){
//出窗口
hash[fruits[left]]--;
if(hash[fruits[left]] == 0)
hash.erase(fruits[left]);
left++;
}
ret = max(ret, right - left + 1);
}
return ret;
}
};
例题6：找到字符串中所有字母异位词
找到字符串中所有字母异位词
不同于之前的题目的是，这道题的滑动窗口是固定长度的（长度为p的大小）
可以用两个哈希表分别表示 p 中每个字符出现的次数 和 滑动窗口中每个字符出现的次数。通过比较两哈希表是否相同判断异位词
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int hash1[26] = {0};//p中每个字符出现的次数
for(auto ch : p) hash1[ch-'a']++;
int hash2[26] = {0};//滑动窗口中每个字符出现的次数
vector<int> ret;
for(int left = 0, right = 0, count = 0; right < s.size(); right++){
char in = s[right];//进窗口的字符
hash2[in - 'a']++;//进窗口
if(hash2[in - 'a'] <= hash1[in - 'a'])
count++;
//判断
if(right - left >= p.size()){//固定的窗口长度:p.size()
char out = s[left++];
if(hash2[out - 'a']-- <= hash1[out - 'a']) count--;//出窗口
}
if(count == p.size()) ret.push_back(left);//更新结果
}
return ret;
}
};
例题7：串联所有单词的子串
串联所有单词的子串
例题6 的加强版，试着将子串当做一整个数据（就像单个字符一样）
class Solution {
public:
vector<int> findSubstring(string s, vector<string>& words) {
unordered_map<string, int> hash1;//存储 words 中的子串
for(auto& str : words) hash1[str]++;
int len = words[0].size();//一个子串的长度，可视作一个整体数据
vector<int> ret;
for(int i = 0; i < len; i++){//自不同的起点出发遍历所有情况
unordered_map<string, int> hash2;//维护滑动数组内的子串
for(int left = i, right = i, count = 0; right + len <= s.size(); right += len){
string in = s.substr(right, len);//进窗口的子串
hash2[in]++;//进窗口
if(hash1.count(in) && hash2[in] <= hash1[in]) count++;
if(right - left >= len * words.size()){
string out = s.substr(left, len);//出窗口的数据
if(hash1.count(out) && hash2[out] <= hash1[out]) count--;
hash2[out]--;
left += len;//出窗口
}
if(count == words.size()) ret.push_back(left);
}
}
return ret;
}
};
例题8：最小覆盖子串
最小覆盖子串
分析：
class Solution {
public:
string minWindow(string s, string t) {
int hash1[58] = { 0 };//开了57个空间，然后不够……建议直接开128个空间，还省去了后面 -'A' 的麻烦
for (auto ch : t) hash1[ch - 'A']++;
int hash2[58] = { 0 };
int begin = -1, len = INT_MAX;
for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
char in = s[right];//进窗口数据
hash2[in - 'A']++;//进窗口
if (hash2[in - 'A'] <= hash1[in - 'A']) count++;
while (count == t.size()) {//判断
if (right - left + 1 < len) {//更新结果
len = right - left + 1;
begin = left;
}
char out = s[left];//出窗口数据
if (hash2[out - 'A'] <= hash1[out - 'A']) count--;
hash2[out - 'A']--;//出窗口
left++;
}
}
return len == INT_MAX ? "" : s.substr(begin, len);
}
};
