目录
1.最大连续1的个数 III
1.题目解析
2.算法原理
2.1暴力枚举（不过多介绍）
2.2双指针优化
3.代码编写
2. 将 x 减到 0 的最小操作数
1.题目解析
2.算法原理
2.1滑动窗口
3.代码编写
3. 水果成篮
1.题目解析
2.算法思路
2.1滑动窗口+哈希表
1.最大连续1的个数 III
1.题目解析
。
2.算法原理
2.1暴力枚举（不过多介绍）
int longestOnes(vector<int>& nums, int k) {
int n = nums.size();
int ret = 0;
for(int i = 0; i<n; i++)
{
int t = k;
int cnt = 0;
for(int j = i; j<n; j++)
{
if(nums[j] == 1)
{
cnt++;
}
else if(nums[j] == 0)
{
t--;
if(t < 0)
{
break;
}
cnt++;
}
ret = max(ret,j-i+1);
}
}
return ret;
}2.2双指针优化
在暴力解法中发现，两个指针是同向一起向后走，考虑双指针优化。
将问题转化为维护一个区间，区间内部的0的个数不能超过k。求最长的区间。
进窗口：遍历数组如果nums[right] == 0,计数器cnt--
判断：区间内0的个数是否超过k
出窗口：left++直到区间内0的个数小于k
3.代码编写
int longestOnes(vector<int>& nums, int k) {
int left = 0,right = 0;
int ret = 0, cnt = 0;
while(right < nums.size())
{
if(nums[right] == 0)
{
cnt++;
}
while(cnt > k)
{
if(nums[left] == 0)
{
cnt--;
}
left++;
}
ret = max(ret,right - left +1);
right++;
}
return ret;
}2. 将 x 减到 0 的最小操作数
1.题目解析
这道乍一看，左边减一次，右边见一次很不好处理，这个时候用逆向思维可以很好解决问题。
让操作次数最短，就是让左右两边的和为x长度加起来最短，转换一下，让中间部分和为sum-x最长（sum为整个数组的和）。
求和为sum-x的最长子数组
2.算法原理
2.1滑动窗口
求数组整体的和sum
进窗口：遍历数组cnt += nums[right]
判断：cnt的值是否大于target
出窗口：cnt -= nums[left]
3.代码编写
int minOperations(vector<int>& nums, int x) {
int sum = 0;
for(int i : nums)
{
sum += i;
}
int target = sum - x;
int n = nums.size();
if(target < 0)return -1;
int cnt = 0;
int ret = -1;
for(int left = 0,right = 0; right < nums.size(); right++)
{
cnt += nums[right];
while(cnt > target)
{
cnt -= nums[left];
left++;
}
if(cnt == target)
ret = max(ret,right-left+1);
}
return ret == -1 ? -1 : n -ret ;
}3.最大连续1的个数 III
1.题目解析
说了一大堆翻译成人话就是
求数字种类不超过2种的最长子数组。（1，2就是不同的水果种类）
2.算法思路
2.1滑动窗口+哈希表
进窗口:进哈希表，数字种类++。
判断：哈希表的大小是否大于2
出窗口：将left指针指向的元素，在哈希表中数字种类--，减为0之后删除，直到哈希表的大小小于2。
int totalFruit(vector<int>& fruits) {
//找一个最长连续的子数组，子数组内的类型不能超过2种
unordered_map<int,int> hash;
int ret = 0;
int left = 0, right = 0;
while(right < fruits.size())
{
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);
right++;
}
return ret;
}
