不定长滑动窗口
3. 无重复字符的最长子串 未解决
题意
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
思路
- 需要熟练运用map，重复想到set或map，连续子串想到窗口
- 要注意这些：
- 一是连续性，abca，滑动到第二个a，删除最左边的就行
- 二是注意这个while可以让指针连续移动，直到重复字符那里
- 三是复杂度O（n），虽然嵌套了 while，但每个字符最多被 left 和 right 各访问一次
代码
class Solution {
public:
int lengthOfLongestSubstring(string s) {
int n = s.length(), ans = 0, left = 0;
unordered_map<char, int> cnt; // 维护从下标 left 到下标 right 的字符
for (int right = 0; right < n; right++) {
char c = s[right];
cnt[c]++;
while (cnt[c] > 1) { // 窗口内有重复字母
//注意，这里不是用count，直接用value就行了
cnt[s[left]]--; // 移除窗口左端点字母
left++; // 缩小窗口
}
ans = max(ans, right - left + 1); // 更新窗口长度最大值
}
return ans;
}
};1493. 删掉一个元素以后全为1的最长子数组 已解决
题意
给你一个二进制数组 nums ，你需要从中删掉一个元素。 请你在删掉元素的结果数组中，返回最长的且只包含 1 的非空子数组的长度。 如果不存在这样的子数组，请返回 0 。
思路
最长的子数组 - 不定长滑动窗口 用样例模拟了一下，发现： 删掉一个元素 - map中的 0 键对应的值 只能为1
那么问题转化为： 只含一个0的最长滑动窗口长度减去1，，，做的时候发现答案也可以是value（1）
代码
class Solution {
public:
int longestSubarray(vector<int>& nums) {
//不定长滑动窗口，问题可以转化为，只含1个0的最长滑动窗口的值减去1
//int，int型的map，
int l = 0, ans = 0;
unordered_map<int,int> mp;
for(int i = 0; i < nums.size(); i++){
mp[nums[i]]++;
while(mp[0] > 1){
mp[nums[l]]--;
l++;
}
ans = max(ans,mp[1]);
}
return mp[0] == 0 ? ans - 1 : ans;
}
};3411. 使数组平衡的最少移除数目 已解决
题意
给你一个整数数组 nums 和一个整数 k。 如果一个数组的 最大 元素的值 至多 是其 最小 元素的 k 倍，则该数组被称为是 平衡 的。 你可以从 nums 中移除 任意 数量的元素，但不能使其变为 空 数组。
返回为了使剩余数组平衡，需要移除的元素的 最小 数量。
注意：大小为 1 的数组被认为是平衡的，因为其最大值和最小值相等，且条件总是成立。
思路
子数组，这个窗口是不断减小的可以先排序吧，排序之后，样例通过 好吧，错误，没有考虑到可以移除最小值 好吧，解答错误，其实也可以移除左边再右边，那么思路应该是 逆向思路，排好序，求符合条件的最长子数组，一旦不符合条件，左指针右移动，更新答案， 返回长度减去最长的子数组长度
代码
class Solution {
public:
int minRemoval(vector<int>& nums, int k) {
//子数组，这个窗口是不断减小的可以先排序吧，排序之后，样例通过
//好吧，错误，没有考虑到可以移除最小值
//好吧，解答错误，其实也可以移除左边再右边，那么思路应该是
//逆向思路，排好序，求符合条件的最长子数组，一旦不符合条件，左指针右移动，更新答案，
//返回长度减去最长的子数组长度
sort(nums.begin(),nums.end());
int n = nums.size(),l = 0,res = 0;
for(int i = 0; i < n; i++){
while(nums[i] > nums[l]*(long long)k){
l++;
}
res = max(res,i - l + 1);
}
return n - res;
}
};1208. 尽可能使字符串相等 未解决
题意
给两个长度相同的字符串，s 和 t。
将 s 中的第 i 个字符变到 t 中的第 i 个字符需要 |s[i] - t[i]| 的开销（开销可能为 0），也就是两个字符的 ASCII 码值的差的绝对值。
用于变更字符串的最大预算是 maxCost。在转化字符串时，总开销应当小于等于该预算，这也意味着字符串的转化可能是不完全的。
如果你可以将 s 的子字符串转化为它在 t 中对应的子字符串，则返回可以转化的最大长度。
如果 s 中没有子字符串可以转化成 t 中对应的子字符串，则返回 0。
思路
...
代码
// 代码904. 水果成篮 已解决
题意
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。
你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
- 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
- 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
- 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。
思路
两个篮子，试试用map的size函数吧， 进入map，当size>=3 左边删，左边出 ans = max.... 不定长
代码
class Solution {
public:
int totalFruit(vector<int>& fruits) {
//两个篮子，试试用map的size函数吧，
//进入map，当size>=3 左边删，左边出
//ans = max....
//不定长
int l = 0, ans = 0;
unordered_map<int,int> mp;
for(int i = 0; i < fruits.size(); i++){
mp[fruits[i]]++;
while(mp.size() > 2){
mp[fruits[l]]--;
if(mp[fruits[l]] == 0) mp.erase(fruits[l]);
l++;
}
ans = max(ans, i - l + 1);
}
return ans;
}
};