LeedCode刷题---滑动窗口问题(二)

顾得泉：个人主页

个人专栏：《Linux操作系统》??《C/C++》??《LeedCode刷题》

键盘敲烂，年薪百万！

---

一、将X减到0的最小操作数

题目链接：将 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 <= 105
• 1 <= nums[i] <= 104
• 1 <= x <= 109

解法

算法思路:

???????题目要求的是数组「左端+右端」两段连续的、和为×的最短数组，信息量稍微多一些，不易理清思路;我们可以转化成求数组内一段连续的、和为sum(nums) - x的最长数组。此时，就是熟悉的滑动窗口问题了。

算法流程:

?????a.转化问题:求target = sum(nums) - ×。如果target < 0，问题无解;

?????b.初始化左右指针l = 0,r = 0(滑动窗口区间表示为[l，r)，左右区间是否开闭很重要，必须设定与代码一致)，记录当前滑动窗口内数组和的变量sum = 0，记录当前满足条件数组的最大区间长度maxLen = -1;

?????c. 当r小于等于数组长度时，一直循环:

? ? ? ? ?i.如果sum < target，右移右指针，直至变量和大于等于target，或右指针已经移到头;

? ? ? ? ?ii.如果sum > target，右移左指针，直至变量和小于等于target，或左指针已经移到头;

? ? ? ? ?ii.如果经过前两步的左右移动使得sum == target，维护满足条件数组的最大长度，并让下个元素进入窗口;

??????d.循环结束后，如果maxLen的值有意义，则计算结果返回;否则，返回-1。

代码实现

class Solution 
{
public:
    int minOperations(vector<int>& nums, int x) 
    {
        int sum = 0;
        for(int a : nums) sum += a;
        int target = sum - x;
        if(target < 0) 
            return -1;
        int ret = -1;
        for(int left = 0, right = 0, tmp = 0; right < 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;
    }
};

---

二、水果成篮

题目链接：水果成篮

题目描述

???????你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组?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 <= 105
• 0 <= fruits[i] < fruits.length

解法

算法思路:

???????研究的对象是一段连续的区间，可以使用「滑动窗口」思想来解决问题。让滑动窗口满足:窗口内水果的种类只有两种。

做法∶

???????右端水果进入窗口的时候，用哈希表统计这个水果的频次。这个水果进来后，判断哈希表的大小；如果大小超过2:说明窗口内水果种类超过了两种。那么就从左侧开始依次将水果划出窗口，直到哈希表的大小小于等于2，然后更新结果;如果没有超过2，说明当前窗口内水果的种类不超过两种，直接更新结果ret。

算法流程:

?????a.初始化哈希表hash来统计窗口内水果的种类和数量;

?????b.初始化变量:左右指针left =0， right =0，记录结果的变量ret= 0;c. 当right小于数组大小的时候，一直执行下列循环:

? ? ? ? ?i.将当前水果放入哈希表中;

? ? ? ? ?ii.判断当前水果进来后，哈希表的大小:

???????如果超过2;将左侧元素滑出窗口，并且在哈希表中将该元素的频次减一;

???????如果这个元素的频次减一之后变成了0，就把该元素从哈希表中删除;。重复上述两个过程，直到哈希表中的大小不超过2;

? ? ? ? ?iii.更新结果ret;

? ? ? ? ?iv. right++，让下一个元素进入窗口;d.循环结束后，ret存的就是最终结果。

代码实现

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)
            {
                hash[f[left]]--;
                if(hash[f[left]] == 0)
                hash.erase(f[left]);
                left++;
            }
            ret = max(ret, right - left + 1);
        }
        return ret;
    }

---

三、找到字符串中所有字母异位词

题目链接：找到字符串中所有字母异位词

题目描述

???????给定两个字符串?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 * 104
• s?和?p?仅包含小写字母

解法

算法思路:

???????因为字符串p的异位词的长度一定与字符串p的长度相同，所以我们可以在字符串s中构造一个长度为与字符串p的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量;当窗口中每种字母的数量与字符串p中每种字母的数量相同时，则说明当前窗口为字符串p的异位词;

???????因此可以用两个大小为26的数组来模拟哈希表，一个来保存s 中的子串每个字符出现的个数，另一个来保存p中每一个字符出现的个数。这样就能判断两个串是否是异位词。

代码实现

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;
    }
};

---

结语：今日的刷题分享到这里就结束了，希望本篇文章的分享会对大家的学习带来些许帮助，如果大家有什么问题，欢迎大家在评论区留言~~~?