优选算法——滑动窗口

滑动窗口

一、leetcode209.长度最小的子数组

题目分析：

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

找出该数组中满足其总和大于等于target的长度最小的连续子数组，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

算法原理：

​ 滑动窗口也叫做同向双指针；使用条件就是：当right指针不回退的时候；使用方式：初始化双指针，进窗口，，判断条件是否成立，出窗口，更新结果；

代码实现：

int minSubArrayLen(int target, vector<int>& nums) {
    int size = nums.size(), sum = 0, len = INT_MAX;
    for (int left = 0, right = 0; right < size; right++) {
        sum += nums[right];   // 进窗口
        while (sum >= target) // 判断
        {
            len = min(len, right - left + 1); // 更新结果
            sum -= nums[left++];              // 出窗口
        }
    }
    if (len == INT_MAX)
        return 0;
    return len;
}

二、leetcode3.无重复的最长字串

题目分析：

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

算法原理：

​ 利用规律使用滑动窗口解决问题；

代码实现：

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

三、leetcode1004.最大连续1的个数

题目分析：

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

算法原理：

​ 找出0的个数小于等于k个的连续的子数组；

​ 也是使用滑动窗口来解决问题；

代码实现：

int longestOnes(vector<int>& nums, int k) {
    int left = 0, right = 0, zero = 0;
    int size = nums.size();
    int len = 0;
    while (right < size) {
        if (nums[right] == 0)
            zero++;
        if (zero <= k)
            len = max(len, right - left + 1);
        while (zero > k) {
            if (nums[left++] == 0)
                zero--;
        }
        right++;
    }
    return len;
}

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

题目分析：

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

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

算法原理：

​ 正难则反，转化为找出最长的子数组长度，使得子数组的所有元素之和为sum-x；返回的长度就是总长度-子数组长度；

代码实现：

class Solution {
    public:
    int minOperations(vector<int>& nums, int x) {
        int total = 0;
        for (auto& e : nums) {
            total += e;
        }
        int target = total - x;
        if (target < 0) {
            return -1;
        }
        int size = nums.size();
        int ret = -1, len = 0, sum = 0;
        for (int left = 0, right = 0, len = 0; right < size; right++) {
            sum += nums[right];
            while (sum > target) {
                sum -= nums[left++];
            }
            if (sum == target) {
                len = max(len, right - left + 1);
                ret = size - len;
            }
        }
        return ret;
    }
};

五、leetcode904.水果成篮

题目分析：

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

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

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

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

算法原理：

​ 本质上就是转换为找出一个最长的子数组，子数组中不超过两种类型的水果；

代码实现：

int totalFruit(vector<int>& fruits) {
    unordered_map<int, int> map;
    int ret = 0;
    int left = 0, right = 0, size = fruits.size();
    while (right < size) {
        map[fruits[right]]++;
        while (map.size() > 2) {
            map[fruits[left]]--;
            if (map[fruits[left]] == 0) {
                map.erase(fruits[left]);
            }
            left++;
        }
        ret = max(ret, right - left + 1);
        right++;
    }
    return ret;
}