1658. 将 x 减到 0 的最小操作数
给你一个整数数组
nums和一个整数x。每一次操作时，你应当移除数组nums最左边或最右边的元素，然后从x中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。如果可以将
x恰好 减到0，返回 最小操作数 ；否则，返回-1。示例 1：
输入：nums = [1,1,4,2,3], x = 5 输出：2 解释：最佳解决方案是移除后两个元素，将 x 减到 0 。
示例 2：
输入：nums = [5,6,7,8,9], x = 4 输出：-1
示例 3：
输入：nums = [3,2,20,1,1,3], x = 10 输出：5 解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。
提示：
1 <= nums.length <= 10(5)
1 <= nums[i] <= 10(4)
1 <= x <= 10(9)
暴力枚举：
我们从左端取一段区间，右端取一段区间，使这两段区间的元素和为x，并且尽可能使得这两段的区间长度小。等价于取一段区间，使得这段区间的元素和为sum-x，并且尽可能使得这段区间长度大。所谓正难则反。
问题转化为找一段子数组，使得子数组的元素和为target=sum-x，尽可能使得这段子数组的长度大。
对于target的小优化，因为x是正数，所以有三种情况，x<sum,x=sum,x>sum三种情况，x<sum,sum-x>0可以正常求解。如果x=sum,说明返回值是nums.size()。如果x>sum，sum-x<0,说明找不到答案，返回-1。
class Solution {
public:
int minOperations(vector<int>& nums, int x) {
int sum = accumulate(nums.begin(), nums.end(), 0);
int target = sum - x;
if (target < 0)
return -1;
else if (target == 0)
return nums.size();
int tmp = 0;
int ret = -1;
for (int i = 0; i < (int)nums.size(); i++) {
tmp = 0;
for (int j = i; j < (int)nums.size(); j++) {
tmp += nums[j];
if (tmp > target)
break;
if (tmp == target)
ret = max(j - i + 1, ret);
}
}
if (ret == -1)
return ret;
else
return nums.size() - ret;
}
};int sum = accumulate(nums.begin(), nums.end(), 0); 计算数组 nums 的所有元素之和。 int target = sum - x; 计算目标值 target，即从总和中减去 x 后需要达到的新和。 if (target < 0)return -1;
else if (target == 0)return nums.size(); 如果目标值 target 小于0，则无法通过操作达到目标，返回-1。如果目标值 target 等于0，表示不需要任何操作，直接返回数组 nums 的大小。 int tmp = 0;int ret = -1; 初始化临时变量 tmp 用于存储子数组的和，初始化结果 ret 为-1，表示初始时没有找到合适的子数组。 for (int i = 0; i < (int)nums.size(); i++) { 使用外层循环遍历数组 nums。 tmp = 0; 在每次外层循环的开始，重置 tmp。 for (int j = i; j < (int)nums.size(); j++) { 使用内层循环从索引 i 开始遍历数组 nums。 tmp += nums[j]; 更新 tmp，将当前元素 nums[j] 添加到子数组和中。 if (tmp > target)break; 如果当前 tmp 大于目标值 target，表示对于i的所有组合都考虑完毕退出内层循环。 if (tmp == target) ret = max(j - i + 1, ret); 如果当前 tmp 等于目标值 target，更新结果 ret 为当前子数组的长度和已知最大子数组长度的较大值。 if (ret == -1)return ret;elsereturn nums.size() - ret;} 如果没有找到合适的子数组，返回-1。否则，返回数组 nums 的大小减去找到的最大子数组长度，这是因为题目要求的是最少操作次数，即移除元素的次数，而不是保留的子数组长度。 时间复杂度和空间复杂度分析 时间复杂度：O(n^2)，其中 n 是数组 nums 的长度。因为代码中有两层循环，外层循环遍历 nums 的每个元素，内层循环在最坏情况下也可能遍历整个 nums。 空间复杂度：O(1)，代码中没有使用额外的存储空间，除了输入和输出之外，只使用了有限的几个变量。
滑动窗口（同向双指针）优化暴力枚举：
维护一个区间[left,right]使得这段区间内的元素和tmp小于等于target。如果加入right元素后tmp>target，此时对于left，与right，right+1......这些元素的组合都不可能等于target，所以直接跳过这些情况。对于left的所有组合全部考虑完毕。left++。并且维护tmp，tmp是[ledt,right]这个区间内的元素和。
对于left++后的left，与left+1,left+2.....right-1，这些数的组合，tmp一定小于target，所以这些情况可以直接跳过不考虑，只需要从right开始考虑即可。如果tmp>target，后面的也不用考虑了，此时对应left的所有组合考虑完毕。以此类推，一直left++直到tmp<=target。
class Solution {
public:
int minOperations1(vector<int>& nums, int x) {
int sum = accumulate(nums.begin(), nums.end(), 0);
int target = sum - x;
if (target < 0)
return -1;
else if (target == 0) return nums.size();
int ret = -1;
for (int left = 0, right = 0, tmp = 0; right < (int)nums.size(); right++) {
tmp += nums[right];
while (tmp > target)
tmp -= nums[left++];
if (tmp == target)
ret = max(ret, right - left + 1);
}
if (ret == -1)
return ret;
else
return nums.size() - ret;
}
};int sum = accumulate(nums.begin(), nums.end(), 0); 计算数组 nums 的所有元素之和。 int target = sum - x; 计算目标值 target，即从总和中减去 x 后需要达到的新和。 if (target < 0)return -1;else if (target == 0) return nums.size(); 如果目标值 target 小于0，则无法通过操作达到目标，返回-1。如果目标值 target 等于0，表示不需要任何操作，直接返回数组 nums 的大小。 int ret = -1; 初始化结果 ret 为-1，表示初始时没有找到合适的子数组。 for (int left = 0, right = 0, tmp = 0; right < (int)nums.size(); right++) { 使用一个滑动窗口，窗口的左右边界分别由 left 和 right 表示，tmp 用来存储当前窗口内部的和。窗口右边界 right 从0开始，遍历整个数组 nums。 tmp += nums[right]; 将当前右边界的元素加到 tmp 上。 while (tmp > target) tmp -= nums[left++]; 如果当前 tmp 大于目标值 target，则缩小窗口，即从左边界开始减少 tmp 的值。 if (tmp == target) ret = max(ret, right - left + 1); 如果当前 tmp 等于目标值 target，更新结果 ret 为当前滑动窗口的长度和已知最大长度的较大值。
}if (ret == -1)return ret;elsereturn nums.size() - ret;} 如果没有找到合适的子数组，返回-1。否则，返回数组 nums 的大小减去找到的最大长度的滑动窗口的大小，这是因为题目要求的是最少操作次数，即移除元素的次数，而不是保留的子数组长度。 时间复杂度和空间复杂度分析 时间复杂度：O(n)，其中 n 是数组 nums 的长度。尽管有循环嵌套，但每个元素在 nums 中只被访问两次（一次是当它进入窗口，一次是当它离开窗口），所以时间复杂度是线性的。 空间复杂度：O(1)，代码中没有使用额外的存储空间，除了输入和输出之外，只使用了有限的几个变量。
904. 水果成篮
你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组
fruits表示，其中fruits[i]是第i棵树上的水果 种类 。你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：
你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。
给你一个整数数组
fruits，返回你可以收集的水果的 最大 数目。示例 1：
输入：fruits = [1,2,1] 输出：3 解释：可以采摘全部 3 棵树。
示例 2：
输入：fruits = [0,1,2,2] 输出：3 解释：可以采摘 [1,2,2] 这三棵树。 如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
示例 3：
输入：fruits = [1,2,3,2,2] 输出：4 解释：可以采摘 [2,3,2,2] 这四棵树。 如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
示例 4：
输入：fruits = [3,3,3,1,2,1,1,2,3,3,4] 输出：5 解释：可以采摘 [1,2,1,1,2] 这五棵树。
提示：
1 <= fruits.length <= 10(5)
0 <= fruits[i] < fruits.length
暴力枚举：
维护区间[i,j]，hash表示[i,j]区间中不同水果的个数。一直扩展区间的长度，如果hash的元素个数大于2，说明对于i的所有组合我们都考虑完毕了，此时i++。
class Solution {
public:
int totalFruit(vector<int>& f) {
unordered_map<int, int> hash;
int ret = 0;
int n = f.size();
for (int i = 0; i < n; i++) {
hash.clear();
for (int j = i; j < n; j++) {
hash[f[j]]++;
if (hash.size() > 2)
break;
ret = max(ret, j - i + 1);
}
}
return ret;
}
};
int totalFruit(vector<int& f) {
定义了 totalFruit 函数，它接受一个整数向量 f 作为参数，并返回一个整数 ret，表示最长子数组的长度。
unordered_map<int, int hash;
定义了一个哈希表 hash，用于存储子数组中每种整数的出现次数。
int ret = 0;int n = f.size();
初始化结果 ret 为0，并获取数组 f 的长度 n。
for (int i = 0; i < n; i++) {
使用外层循环遍历数组 f。
hash.clear();
在每次外层循环的开始，清空哈希表 hash。
for (int j = i; j < n; j++) {
使用内层循环从索引 i 开始遍历数组 f。
hash[f[j]]++;
更新哈希表 hash，计算子数组中每种整数的出现次数。
if (hash.size() > 2)break;
如果哈希表 hash 的大小超过2，说明子数组中包含超过两种整数，退出内层循环。
ret = max(ret, j - i + 1);
如果当前子数组只包含两种或两种以下的整数，更新结果 ret 为当前子数组的长度和已知最长子数组长度的较大值。
时间复杂度和空间复杂度分析
时间复杂度：O(n^2)，其中 n 是数组 f 的长度。因为代码中有两层循环，外层循环遍历 f 的每个元素，内层循环在最坏情况下也可能遍历整个 f。
空间复杂度：O(n)，在最坏的情况下，当数组 f 中所有元素都不相同时，哈希表 hash 将存储 n 个键值对。
滑动窗口（同向双指针）优化暴力枚举，使用容器模拟哈希表：
对于区间[left,right]，如果新加入进来的right使得区间内水果的种类数大于2，那么对于left的所有组合全部考虑完毕，但是这里有一个隐含的信息，那就是[left,right-1]区间的水果种类数为2。
left++后，如果[left,right-1]区间内的水果种类数没有发生改变，那么对于left与left+1.....right-1这些组合都不需要考虑，因为长度一定小于left++前的长度，此时只需要从right组合开始考虑。此时很显然[left,right]区间的水果种类数是3，所以对应left的所有组合也全部考虑完毕，继续left++。直到区间内水果种类数为2。
如果[left,right-1]区间内的水果种类数发生改变，那么[left,right]区间内水果的种类个数为2，left与left+1...right-1的组合不需要考虑，因为长度一定小于left与right的组合的长度。
区间[left,right]，hash表记录这个区间内不同水果种类数，只需要一直维护想·和这个区间即可。
class Solution {
public:
int totalFruit(vector<int>& f) {
unordered_map<int, int> hash;
int ret = 0;
for (int left = 0, right = 0; right < f.size(); right++) {
hash[f[right]]++;
while (hash.size() > 2)
if (--hash[f[left++]] == 0)
hash.erase(f[left-1]);
ret = max(ret, right - left + 1);
}
return ret;
}
};滑动窗口（同向双指针）优化暴力枚举，使用数组模拟哈希表：
class Solution {
public:
int totalFruit(vector<int>& f) {
int hash[100001] = {0};
int ret = 0;
for (int left = 0, right = 0, kinds = 0; right < f.size(); right++) {
if (hash[f[right]]++ == 0)
kinds++;
while (kinds > 2)
if (--hash[f[left++]] == 0)
kinds--;
ret = max(ret, right - left + 1);
}
return ret;
}
};int totalFruit(vector<int>& f) {
定义了 totalFruit 函数，它接受一个整数向量 f 作为参数，并返回一个整数 ret，表示最长子数组的长度。
int hash[100001] = {0};
定义了一个固定大小的数组 hash，假设数组 f 中的元素不会超过 100000。hash 用于存储子数组中每种整数的出现次数。
int ret = 0;
初始化结果 ret 为0。
for (int left = 0, right = 0, kinds = 0; right < f.size(); right++) {
使用一个滑动窗口，窗口的左右边界分别由 left 和 right 表示，kinds 用来计数当前窗口内部，不同整数的种类数。窗口右边界 right 从0开始，遍历整个数组 f。
if (hash[f[right]]++ == 0) kinds++;
如果 hash 数组中 f[right] 对应的值在增加之前为0，说明遇到了一个新种类的整数，kinds 加1。
while (kinds > 2)
如果当前窗口内的不同整数种类数 kinds 超过2，需要缩小窗口。
if (--hash[f[left++]] == 0) kinds--;
从窗口左边开始，逐个减少 hash 数组中对应整数的计数，如果某个整数的计数减到0，说明该整数已经不在当前窗口内，kinds 减1。
ret = max(ret, right - left + 1);
在每次右边界向右移动后，更新结果 ret 为当前窗口的长度和已知最长子数组长度的较大值。
时间复杂度和空间复杂度分析
时间复杂度：O(n)，其中 n 是数组 f 的长度。尽管有循环嵌套，但每个元素在 f 中只被访问两次（一次是当它进入窗口，一次是当它离开窗口），所以时间复杂度是线性的。
空间复杂度：O(1)，尽管 hash 数组的大小是固定的 100001，但这个大小不依赖于输入数据的大小，因此可以认为是常数空间。
438. 找到字符串中所有字母异位词
给定两个字符串
s和p，找到s中所有p的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。
示例 1:
输入: s = "cbaebabacd", p = "abc" 输出: [0,6] 解释: 起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。 起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。
示例 2:
输入: s = "abab", p = "ab" 输出: [0,1,2] 解释: 起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。 起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。 起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。
提示:
1 <= s.length, p.length <= 3 * 10(4)
s和p仅包含小写字母
暴力枚举：
首先我们需要解决一个问题，那就是判断[i,j]区间里面是否为p的异位词。
如果[i,j]区间是p的异位词，那么[i,j]区间的长度j-i+1至少要等于p的长度。
其实，[i,j]区间内的字符个数，依次与p字符串中的字符个数相同。对应字符种类的个数是相同的。
满足这两个条件，就可以说[i,j]区间是p的异位词。
因此我们可以用一个大小为26的数组hash2模拟hash表，数组的下标对应每一个字符，数组的元素表示对应字符的个数。用一个大小为26的数字hash1模拟hash表，存储p字符串的每一个字符的个数。我们只要每一次都遍历一遍hash1和hash2，看对应的字符能否匹配上个数即可。
在这里我们使用一个count优化。count记录的是hash2中对应hash1的有效字符。先把j位置的字符添加进hash2中，如果hash2[s[j]-'a']<=hash1[s[j]-'a']，说明新加入的字符是有效的字符，count++，这样我们只需要判断count是否等于p.size()就可以判断hash1与hash2是否能够对应字符匹配上数字。
也就是我们可以赋予一些意义，规定。
例如我们规定[i,j]区间，hash1存储的是p字符串的字符个数，hash2存储的是[i,j]区间的字符个数，count记录hash2中有效的字符，m记录hash1的长度。我们只需要一直维护这些定义。每添加进一个j元素，我们就可以判断[i,j]是否是p的异位词，count==m即可。当我们的[i,j]区间长度大于m，就说明与i的所有组合都考虑完毕，i++。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int hash1[26] = {0};
for (auto ch : p)
hash1[ch - 'a']++;
int hash2[26] = {0};
int m = p.size();
int n = s.size();
for (int i = 0; i < n; i++) {
int count = 0;
memset(hash2, 0, sizeof(hash2));
for (int j = i; j < n; j++) {
char in = s[j];
hash2[s[j] - 'a']++;
if (hash2[s[j] - 'a'] <= hash1[s[j] - 'a'])
count++;
if (j - i + 1 > m)
break;
if (count == m)
ret.push_back(i);
}
}
return ret;
}
};vector<int> findAnagrams(string s, string p) {
定义了 findAnagrams 函数，它接受两个字符串参数 s 和 p，并返回一个整数向量，存储所有异位词的起始索引。
vector<int> ret;
初始化一个向量 ret，用于存储结果。
int hash1[26] = {0};
定义了一个数组 hash1，用于存储字符串 p 中每个字符出现的次数。由于 p 中只包含小写字母，所以数组大小为26。
for (auto ch : p) hash1[ch - 'a']++;
遍历字符串 p，更新 hash1 数组，计算 p 中每个字符的出现次数。
int hash2[26] = {0};
定义了一个数组 hash2，用于存储字符串 s 的子串中每个字符出现的次数。
int m = p.size();int n = s.size();
定义了两个整数 m 和 n，分别存储字符串 p 和 s 的长度。
for (int i = 0; i < n; i++) {
使用外层循环遍历字符串 s。
int count = 0;
初始化一个计数器 count，用于跟踪当前子串中与 p 中字符匹配的字符数量。
memset(hash2, 0, sizeof(hash2));
在每次外层循环的开始，重置 hash2 数组。
for (int j = i; j < n; j++) {
使用内层循环遍历字符串 s，从索引 i 开始。
char in = s[j];
取出当前需要加入hash2中的字符 in，也就是进去区间的窗口的字符。
hash2[s[j] - 'a']++;
更新 hash2 数组，计算当前子串中每个字符的出现次数。
if (hash2[s[j] - 'a'] <= hash1[s[j] - 'a']) count++;
如果当前字符在子串中的出现次数不超过它在 p 中的出现次数，则增加 count，统计hash2中有效的字符个数。
if (j - i + 1 m)break;
如果当前子串的长度超过了 p 的长度，则退出内层循环，此时对于i的所有组合都考虑完毕。
if (count == m) ret.push_back(i);
如果 count 等于 p 的长度，说明找到了一个异位词，将其起始索引 i 加入结果向量 ret。
时间复杂度和空间复杂度分析
时间复杂度：O(n * m)，其中 n 是字符串 s 的长度，m 是字符串 p 的长度。因为代码中有两层循环，外层循环遍历 s，内层循环在最坏情况下需要遍历整个 s。
空间复杂度：O(1)，因为 hash1 和 hash2 的大小固定为26，不随输入数据的大小而变化。
滑动窗口（同向双指针）优化暴力枚举：
我们在上述暴力枚举中，我们一直维护m个区间长度的区间，从i一直枚举到n-1。当i++的时候，我们没必要重新维护hash2和count。我们只需要在区间长度大于m的时候，从hash2和count中维护丢弃i这个元素即可。如果要从hash2中丢弃字符，丢弃前判断hash2[s[j]-'a']<=hash1[s[j]-'a']，如果成立，那么这个被丢弃的字符是有效字符，count--。如果维护hash2[out - 'a']--。
class Solution {
public:
vector<int> findAnagrams(string s, string p) {
vector<int> ret;
int hash1[26] = {0};
for (auto ch : p)
hash1[ch - 'a']++;
int hash2[26] = {0};
int m = p.size();
for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
char in = s[right];
if (++hash2[in - 'a'] <= hash1[in - 'a'])
count++;
if (right - left + 1 > m) {
char out = s[left++];
if (hash2[out - 'a']-- <= hash1[out - 'a'])
count--;
}
if (count == m)
ret.push_back(left);
}
return ret;
}
};vector<int> findAnagrams(string s, string p) {
定义了 findAnagrams 函数，它接受两个字符串参数 s 和 p，并返回一个整数向量 ，存储所有异位词的起始索引。
vector<int> ret;
初始化一个向量 ret，用于存储结果。
int hash1[26] = {0};
定义了一个数组 hash1，用于存储字符串 p 中每个字符出现的次数。由于 p 中只包含小写字母，所以数组大小为26。
for (auto ch : p) hash1[ch - 'a']++;
遍历字符串 p，更新 hash1 数组，计算 p 中每个字符的出现次数。
int hash2[26] = {0};
定义了一个数组 hash2，用于存储当前考察的字符串 s 的子串中每个字符出现的次数。
int m = p.size();
定义了一个整数 m，存储字符串 p 的长度。
for (int left = 0, right = 0, count = 0; right < s.size(); right++) {
使用一个滑动窗口，窗口的左右边界分别由 left 和 right 表示，count 用来计数当前窗口内部，满足条件的字符个数,也就是有效字符个数。窗口右边界 right 从0开始，遍历整个字符串 s。
char in = s[right];
获取当前右边界指向的字符 in，也就是需要加入窗口的字符。
if (++hash2[in - 'a'] <= hash1[in - 'a']) count++;
先将 in 对应的 hash2 数组值加1，然后比较 hash2[in - 'a'] 和 hash1[in - 'a']，如果 hash2 的值不大于 hash1 的值，说明当前字符 in 是有效字符，count 加1。
if (right - left + 1 m) {
如果当前窗口的大小超过了字符串 p 的长度 m，则需要将窗口左边界向右移动。
char out = s[left++];
获取当前左边界指向的字符 out，并将左边界向右移动一位。
if (hash2[out - 'a']-- <= hash1[out - 'a']) count--;
先减少 out 对应的 hash2 数组值，然后比较 hash2[out - 'a'] 和 hash1[out - 'a']，如果在减少之前 hash2 的值不大于 hash1 的值，说明移除的是一个有效字符，count 减1。
if (count == m) ret.push_back(left);
如果 count 等于 p 的长度 m，说明当前窗口内的字符与 p 中的字符完全匹配，将窗口左边界 left 添加到结果向量 ret 中。
时间复杂度和空间复杂度分析
时间复杂度：O(n)，其中 n 是字符串 s 的长度。尽管内部有循环，但每个字符在 s 中只被访问两次（一次是当它进入窗口，一次是当它离开窗口），所以时间复杂度是线性的。
空间复杂度：O(1)，因为 hash1 和 hash2 的大小固定为26，不随输入数据的大小而变化。
结尾
最后，感谢您阅读我的文章，希望这些内容能够对您有所启发和帮助。如果您有任何问题或想要分享您的观点，请随时在评论区留言。
同时，不要忘记订阅我的博客以获取更多有趣的内容。在未来的文章中，我将继续探讨这个话题的不同方面，为您呈现更多深度和见解。
谢谢您的支持，期待与您在下一篇文章中再次相遇！
