目录
1. 长度最小的子数组
2. 无重复字符的最长子串
3. 最大连续1的个数
4. 将X减到0的最小操作数
5. 水果成篮
6. 找到字符串中所有字母异位词
7. 最小覆盖子串
8. 串联所以单词的子串
1. 长度最小的子数组
209. 长度最小的子数组
https://leetcode.cn/problems/minimum-size-subarray-sum/
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, …, numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int add=0,left=0,right=0,count=INT_MAX;
for(left,right;right<nums.size();right++)
{
add+=nums[right];
while(add>=target)
{
count=min(count,right-left+1);
add-=nums[left++];
}
}
return count==INT_MAX?0:count;
}
};
2. 无重复字符的最长子串
3. 无重复字符的最长子串https://leetcode.cn/problems/longest-substring-without-repeating-characters/
给定一个字符串 s ，请你找出其中不含有重复字符的 最长 子串 的长度。
写法一:
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int res = 0;
int len = s.size();
int freq[128] = {0};
int left = 0, right = -1;
while (left < len) {
if (right + 1 < len && freq[s[right + 1]] == 0) {
freq[s[++right]]++;
} else {
freq[s[left++]]–;
}
res = max(res, right – left + 1);
}
return res;
}
};
思路：利用数组充当哈希表，统计单词出现的个数
写法二：
class Solution {
public:
int lengthOfLongestSubstring(string s) {
size_t count=0;
string copys;
for(int i=0;i<s.size();i++)
{
size_t d=copys.find(s[i]);
if(d==string::npos)
{
copys.push_back(s[i]);
count=max(copys.size(),count);
}
else
{
copys = copys.substr(d + 1) + s[i];
}
}
return count;
}
};
思路：创建新的字符串，不同就插入，相同就保留字符串后面的部分。
3. 最大连续1的个数
1004. 最大连续1的个数 IIIhttps://leetcode.cn/problems/max-consecutive-ones-iii/
给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int left=0,right=0,maxi=0;
map<int,int> kv;
if(k>=nums.size())
return nums.size();
while(right<nums.size())
{
kv[nums[right++]]++;
while(kv[0]>k)
{
kv[nums[left++]]–;
}
maxi=max(maxi,kv[0]+kv[1]);
}
return maxi;
}
};
思路：不定长窗口，如果窗口内没有k个0，遇到1就扩大，有的话就滑动。
4. 将X减到0的最小操作数
1658. 将 x 减到 0 的最小操作数https://leetcode.cn/problems/minimum-operations-to-reduce-x-to-zero/
给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。
如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int left=0,right=0,add=0,sum=0,maxi=INT_MIN;
for(auto&e:nums)
{
sum+=e;
}
if(x>sum)
return -1;
while(right<nums.size())
{
add+=nums[right++];
while(add>sum-x)
add-=nums[left++];
if(add==sum-x)
maxi=max(maxi,right-left);
}
if(maxi==INT_MIN)
return -1;
return nums.size()-maxi;
}
};
思路：等价于在数组中间找和为sum-x的最长数组，然后通过剩余个数就知道操作数
5. 水果成篮
904. 水果成篮https://leetcode.cn/problems/fruit-into-baskets/
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int left=0,right=2,maxi=0;
map<int,int> kv;
if(fruits.size()<=2)
return fruits.size();
kv[fruits[0]]++;
kv[fruits[1]]++;
while(right<fruits.size())
{ //此时它不是篮子里的品种，并且已经放入了，要不断拿出
//直到只剩一个品种
while(kv[fruits[right]]==0&&kv.size()>2)
{
kv[fruits[left]]–;
if(kv[fruits[left]]==0)
kv.erase(fruits[left]);
left++;
}
kv[fruits[right++]]++;
maxi=max(maxi,right-left);
}
return maxi;
}
};
思路：滑动窗口遍历数组，保持篮子中只有两个品种水果,不断统计篮子里的个数，取最大。
6. 找到字符串中所有字母异位词
438. 找到字符串中所有字母异位词https://leetcode.cn/problems/find-all-anagrams-in-a-string/
给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
int left = 0, right=0;
vector<int> v;
map<char,int> kv,kv2;
if (p.size() > s.size())
return v;
for(auto& e:p)//原表
kv[e]++；
int i=0;
while(i<p.size())//创建窗口：表
{
kv2[s[i]]++;
i++;
}
right=left+p.size()-1;
while(right < s.size()) {
if(kv2==kv) //表相同
v.push_back(left);
if(right==s.size()-1)
break;
kv2[s[right+1]]++;
kv2[s[left]]–;
if(kv2[s[left]]==0)
kv2.erase(s[left]);
left++;
right++;
}
return v;
}
};
思路：创建两张表，分别用于对比和统计，滑动窗口遍历，找窗口内满足异位的情况。
7. 最小覆盖子串
LCR 017. 最小覆盖子串https://leetcode.cn/problems/M1oyTv/
给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。
如果 s 中存在多个符合条件的子字符串，返回任意一个。
注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量
class Solution {
public:
string minWindow(string s, string t) {
int left = 0, right = 0, count = 0;
int minLen = INT_MAX;
string str, st;
unordered_map<char, int> kv1; // 记录 t 中字符需求
unordered_map<char, int> kv2; // 当前窗口字符统计
if (t.size() > s.size())
return "";
for (auto& e : t)
kv1[e]++;
while (right < s.size()) {
auto it = kv1.find(s[right]);
if (it != kv1.end()) {//找到符合，统计单个字符数量
kv2[s[right]]++;
if (kv2[s[right]] == kv1[s[right]])
//如果数量相同，则成功统计一个，直到都统计完成
count++;
}
str.push_back(s[right]);
while (count == kv1.size()) { //全部统计完成，开始滑动窗口
if (right – left + 1 < minLen) {
minLen = right – left + 1;
st = str;
}
auto it1 = kv1.find(s[left]);
if (it1 != kv1.end()) {
if (kv2[s[left]] == kv1[s[left]])
count–;
kv2[s[left]]–;
}
if (!str.empty())
str.erase(str.begin());
left++;
}
right++;
}
return minLen == INT_MAX ? "" : st;
}
};
思路：与上题类似，都是创建双表对比，但本题要尤其注意统计逻辑，会有很多复杂情况需要处理，且str的插入删除情况很复杂，不易理解。
8. 串联所以单词的子串
30. 串联所有单词的子串https://leetcode.cn/problems/substring-with-concatenation-of-all-words/
给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。
s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。
- 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。
返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。
class Solution {
public:
bool check(string& s,unordered_map<string, int> freq,int& lw,int& length)
{
string str;
int i=0;
bool result=false;
while(i<=length)
{
if(str.size()==lw)//单词组成，判断情况
{
auto it = freq.find(str);
if(it!=freq.end()&& it->second > 0)//成功找到
{
result=true;
it->second–;
str.clear();//重置条件
}
else
return false;
}
if(i==length)
break;
str.push_back(s[i++]);//插入组成单个单词
}
return result;
}
vector<int> findSubstring(string s, vector<string>& words) {
int left=0,right=0,sz=words.size();
string str;
int lw=words[0].size();//单个单词长度
int length = lw * words.size();//子串长度
right=length-1;
unordered_map<string, int> freq;
for (auto& w : words)
freq[w]++;
vector<int> v;
while(right<s.size())//遍历s的条件
{
string str = s.substr(left,length);
if(check(str,freq,lw,length)==true)//判断当前窗口的合理性
{
v.push_back(left);
}
right++; //正常遍历
left++;
}
return v;
}
};
思路：遍历字符串，以定长窗口滑动找出符合单词的子串的位置，此题巧妙运用哈希表，提高了运行效率。
