【算法一周目】滑动窗口（1）

HZzzzzLu

发布于 2024-11-26 08:26:15

9600

代码可运行

文章被收录于专栏：codingcoding

运行总次数：0

代码可运行

长度最小的子数组

题目链接：209. 长度最小的子数组 题目描述： 给定一个含有 n 个正整数的数组 nums 和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。

解题思路

解法一：暴力求解

枚举所有可能的子数组，计算子数组的和，检查是否大于等于 target ，找到符合题目要求的长度最小的子数组。



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

暴力解法简单粗暴，但是由于时间复杂度是 O(n ^ 2)，一旦数据量比较大，必定会超时

解法二：滑动窗口

滑动窗口其实也是基于暴力解法优化而来，滑动窗口的核心就是想办法让暴力解法中的 right 指针不回退，一直往前走。

我们想想这样一个问题，在暴力解法中，当left和right找到一个合法的子数组后，left++，right有必要回退到left位置吗？答案是没有必要的，当left++后，left和right区间的子数组的和可能大于等于target，也可能小于target。我们可以让left一直++，并在此过程中记录区间长度，直到left和right区间的子数组的和小于target，然后再让right++，增大区间长度的和，重复上述过程，直到遍历完数组。

滑动窗口具体过程如下：

1.初始化left和right指针为0。
2.进窗口：计算区间的和
3.判断：
当区间和大于等于target时，找到合法区间，更新结果，出窗口：让left++，重复判断-更新结果过程，直到区间和小于target；
当区间和小于target时，进窗口：让right++，计算区间和。
4.重复上述过程，直到right遍历完数组。

值得注意的是，更新结果这步不是固定的，有时候在判断时更新，有时候在判断完后再更新。

代码实现

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

细节：由于求的是长度最小的子数组，所以len要初始化为INT_MAX，不能初始化为0。

时间复杂度：O(n)

空间复杂度：O(1)

无重复字符的最大字串

题目链接：3. 无重复字符的最长子串 题目描述：给定一个字符串 s，请你找出其中不含有重复字符的最长子串的长度。

解题思路

解法一：暴力求解

通过枚举从每个位置开始，向后寻找无重复字符的子串能到达的位置，记录其中最长的子串长度即可。在寻找无重复子串时，可以使用哈希表统计字符出现的频次，遇到重复字符时停止。

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;  // 记录结果
        int n = s.length();
        
        // 枚举从不同位置开始的无重复子串
        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 = max(ret, j - i + 1);  // 更新结果
            }
        }
        return ret;
    }
};

暴力求解的问题还是时间复杂度是O(n)，对于处理数据量比较大的数据时会超时。

解法二：滑动窗口

使用滑动窗口，使得窗口内的字符不重复。

当窗口右端进入新字符时，更新哈希表记录字符频次：

如果字符频次大于1，则窗口出现重复字符，开始从左侧收缩窗口，直到字符频次变为1，更新结果。
如果没有超过1，说明没有重复字符，直接更新结果。

代码实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int hash[128] = { 0 };  // 使用数组模拟哈希表
        int left = 0, right = 0, n = s.size(), len = 0;
        while(right < n)
        {
            hash[s[right]]++;  // 将右端字符加入窗口
            while(hash[s[right]] > 1)  //判断
                hash[s[left++]]--;      //出窗⼝
            //更新结果
            len = max(len, right - left + 1); 
            //让下⼀个元素进⼊窗⼝
            right++;    
        }
        return len;
    }
};

细节：由于s由英文字母、数字、符号和空格组成，不必真的使用unordered_map，用一个128大小的数组当作哈希表即可。

时间复杂度：O(n)

空间复杂度：O(1)

最大连续1的个数l l l

题目链接：1004. 最大连续 1 的个数 III 题目描述：给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个0，则返回数组中连续 1的最大个数。

解题思路

根据题目描述，我们可以将其转换为求一段最长的连续子区间，其中0的数量不超过k个，我们用滑动窗口解决。

1.初始化左右指针left和right，以及记录0个数的变量cnt。
2.当right向右遍历数组时：
如果当前元素是0，cnt++；
然后判断cnt是否大于cnt，大于则让left++缩减窗口，移除窗口中的0，直到cnt小于等于k。
3。此时窗口合法，更新结果。

代码实现

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0, cnt = 0, n = nums.size();
        for(int left = 0, right = 0; right < n; right++)
        {
            if(nums[right] == 0) cnt++; //当前元素为0，cnt++
            
            //当cnt > k时，移除窗口中的0，直到cnt <= k
            while(cnt > k)
            {
                if(nums[left] == 0)
                    cnt--;
                left++;    
            }
            //更新结果
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

时间复杂度：O(n)

空间复杂度：O(1)

将x减到0的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数

题目描述： 给你一个整数数组 nums 和一个整数 x。每次操作时，你可以移除数组 nums 的最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，你需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0，返回最少的操作数；否则，返回 -1。

解题思路

解法：滑动窗口

题目要求的是在数组左端、右端找两段连续且和为x的短数组，我们可以将其转换为在数组中找到和为 sum - x 的最长子数组，其剩余数组长度就是最小操作数，可以使用滑动窗口解决问题。

具体过程如下：

1.计算数组的和 sum ，然后求出target = sum - x。这里有个小细节，若target < 0，说明x > sum，不可能找到题目要求的最小操作数，直接返回-1。
2.初始化 left 和 righ t两个指针为0，再用一个变量 part_sum 记录区间长度的和。
3.当 part_sum > target 时，减小 part_sum，left++，直到 part_sum <= target。
4.如果 part_sum == target，更新最长子数组的长度。
5.right++，增大 part_sum。
循环上述过程，直到 right 遍历完数组。

代码实现

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        //1.计算数组总和
        int n = nums.size(), sum = 0;
        for(auto e : nums) sum += e;

        int len = -1, target = sum - x, part_sum = 0;
        if(target < 0) return -1;
        
        //2.使用滑动窗口求出符合条件的最大子数组和
        for(int left = 0, right = 0; right < n; right++)
        {
            part_sum += nums[right];
            while(left < n && part_sum > target)
                part_sum -= nums[left++];
            if(part_sum == target)
                len = max(len, right - left + 1);
        }

        return len == -1 ? -1 : n - len;
    }
};

拜拜，下期再见😏

摸鱼ing😴✨🎞