【优选算法-滑动窗口】长度最小的子数组、无重复字符的最长子串、最大连续1的个数、将x减为0的最小操作数、水果成篮

一、长度最小的子数组

题目链接：

209. 长度最小的子数组 - 力扣（LeetCode）

题目介绍：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其总和大于等于 target 的长度最小的 子数组

[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

思路1：暴力枚举

每次固定一个起始下标，往后遍历求和，直到大于target停止，并更新最小长度

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        // 记录结果
        int ret = INT_MAX;
        int n = nums.size();
        // 枚举出所有满⾜和⼤于等于 target 的⼦数组[start, end]
        // 由于是取到最⼩，因此枚举的过程中要尽量让数组的⻓度最⼩
        // 枚举开始位置
        for (int start = 0; start < n; start++) {
            int sum = 0; // 记录从这个位置开始的连续数组的和
            // 寻找结束位置
            for (int end = start; end < n; end++) {
                sum += nums[end]; // 将当前位置加上

                if (sum >= target) // 当这段区间内的和满⾜条件时
                {
                    // 更新结果，start 开头的最短区间已经找到
                    ret = min(ret, end - start + 1);
                    break;
                }
            }
        }
        // 返回最后结果
        return ret == INT_MAX ? 0 : ret;
    }
};

思路2：对思路1进行优化（滑动窗口）

思路1在从一个下标开始，计算完后，sum会重新归为0，从下一个下标开始重新计算求和，但是这里有一个问题，第一次求和与第二次求和只相差了一个元素的值，如果直接从头开始，就会产生重重复的计算，所以每当我们从一个下标计算完最小长度后，可以利用单调性，不让sum归0，也不改变end了，直接让sum -= nums[start] ，然后让start++，这样就可以继续向后计算了，但是要注意的是，最左边的值可能是一个很小的值，甚至，sum减去它以后还是满足大于target的，所以这里不能用if判断，而是用一个while循环。

这样在一个连续空间上，两个指针同向移动就叫做滑动窗口

时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者最多都往后移动 n 次。因此时间复杂度是 O(N) 。

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int  minlen=INT_MAX;
        int sum=0;
        for(int left=0,right=0;right<nums.size();right++)
        {
            sum+=nums[right];
            while(sum>=target)
            {
                minlen=min(minlen,right-left+1);
                sum-=nums[left];
                left++;
            }
        }
        return minlen==INT_MAX?0:minlen;;
    }
};

二、无重复字符的最长子串

题目链接：

3. 无重复字符的最长子串 - 力扣（LeetCode）

题目介绍:

给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

0 <= s.length <= 5 * 104
s 由英文字母、数字、符号和空格组成

思路1：暴力枚举

依旧是从一个下标开始遍历，判断是否出现重复字符串可以利用哈希表，当hash[n]>1时就说明有重复字符了

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0; // 记录结果
        int n = s.length();
        // 1. 枚举从不同位置开始的最⻓重复⼦串
        // 枚举起始位置
        for (int i = 0; i < n; i++) {
            // 创建⼀个哈希表，统计频次
            int hash[128] = {0};

            // 寻找结束为⽌
            for (int j = i; j < n; j++) {
                hash[s[j]]++;       // 统计字符出现的频次
                if (hash[s[j]] > 1) // 如果出现重复的
                    break;

                // 如果没有重复，就更新 ret
                ret = max(ret, j - i + 1);
            }
        }
        // 2. 返回结果
        return ret;
    }
};

思路2：滑动窗口

研究的对象依旧是⼀段连续的区间，因此继续使用「滑动窗口」思想来优化。

让滑动窗口满足：窗口内所有元素都是不重复的。做法：

右端元素 ch 进⼊窗口的时候，哈希表统计这个字符的频次：

如果这个字符出现的频次超过 1 ，说明窗口内有重复元素，那么就从左侧开始划出窗口，直到 ch 这个元素的频次变为 1 ，然后再更新结果。
如果没有超过1 ，说明当前窗口没有重复元素，可以直接更新结果

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = {0};
        int maxlen = 0;
        for (int left = 0, right = 0; right < s.size(); right++) {
            hash[s[right]]++;
            while (hash[s[right]] > 1) {
                hash[s[left]]--;
                left++;
            }
            maxlen = max(maxlen, right - left + 1);
        }
        return maxlen;
    }
};

三、最大连续 1 的个数 III

题目链接：

1004. 最大连续1的个数 III - 力扣（LeetCode）

题目介绍：

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

思路：

不用想着翻转元素，这样反而会把题目搞复杂，转变一下思路，这个题目就是找一个0的个数不大于k个的连续区间的最大长度，同样的在一段连续区间上操作，可以采用滑动窗口。

定义一个变量num用于记录窗口中0的个数，每次让nums[right]入窗口，如果他的值是0的话，就让num++，如果num>k,就从左边出窗口，直到 num <= k,再更新结果；如果入窗口后，num还是小于k的，说明这段区间是符合要求的，可以直接更新结果

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int num=0;
        int maxlen=INT_MIN;
        for(int left=0,right=0;right<nums.size();right++)
        {
            if(nums[right]==0)
                num++;
            while(num>k)
            {
                if(nums[left]==0)
                {
                    left++;
                    num--;
                }
                else
                {
                    left++;
                }
            }
            maxlen=max(maxlen,right-left+1);
        }
        return maxlen;
    }
};

四、将 x 减到 0 的最小操作数

题目链接：

1658. 将 x 减到 0 的最小操作数 - 力扣（LeetCode）

题目介绍：

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要修改数组以供接下来的操作使用。

如果可以将 x 恰好减到 0 ，返回 最小操作数 ；否则，返回 -1 。

1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109

思路：

这个题目如果从正面想的话比较复杂，因为它是从数组两边进行操作的，所以我们可以转变一下思路，将这个题变为找一段最长连续区间的和=sum - x，这样最小操作数就是数组的长度减去这个连续区间的长度了。

首先计算出数组的和，然后求出sum-x，如果target的值都小于0了，就返回1，因为数组中的元素都是大于0的。

接下来就可以让right入窗口了，如果和大于target的话，就出窗口，直到和小于等于target，要注意更新结果要有一个判断条件，就是 sum=target

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        //转变思路，求一段连续空间中和为sum-x的长度
        int sum=0;
        for(auto& e: nums)
        {
            sum+=e;
        }
        int target=sum-x;
        if(target<0)
        return -1;
        int maxlen=-1;
        sum=0;
        for(int left=0,right=0;right<nums.size();right++)
        {
            sum+=nums[right];
            
            while(sum>target)
            {
                sum-=nums[left++];
            }
            if(sum==target)
            maxlen=max(maxlen,right-left+1);
        }
        if(maxlen==-1)
        return -1;
        else
        return nums.size()-maxlen;
    }
};

五、水果成篮

题目链接：

904. 水果成篮 - 力扣（LeetCode）

题目介绍：

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果种类。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

你只有两个篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
你可以选择任意一棵树开始采摘，你必须从每棵树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的最大数目。

思路：

这个题目依旧是操作一个连续的空间，也要遍历，所以可以采用滑动窗口，让滑动窗口维护只有两类水果。

当一个水果入窗口后，可以将他的种类用哈希表维护起来，这样当一个新水果进来后，哈希表的长度就会加1，如果哈西表的长度大于2的话，说明窗口中存在第三种水果了，那就从左边出窗口，直到哈希表的长度小于2

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> m;
        int num=0;
        for(int left=0,right=0;right<fruits.size();right++)
        {
           m[fruits[right]]++;

           while(m.size()>2)
           {
                m[fruits[left]]--;
                if(m[fruits[left]]==0)
                m.erase(fruits[left]);
                left++;
           }
           num=max(num,right-left+1);
        }
        return num;
    }
};