[算法初阶]第二集 滑动窗口(已完结)

大家好啊,好久没有更新了,最近比较忙,所以来更新初阶算法,正好复习一下,感谢大家的观看,如有错误欢迎指出。

下面我们来看题目吧！

1.209. 长度最小的子数组

这题大家想必一眼就看出了解法一暴力法

这个解法很简单

代码如下,不做多的解释

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

这个解法时间复杂度是O()其中 n 是数组的长度。需要遍历每个下标作为子数组的开始下标，对于每个开始下标，需要遍历其后面的下标得到长度最小的子数组。

但是这不是我们要学的思路,我们要探究的是另一种的解法——滑动窗口

该解法思路：

定义两个指针 start 和 end 分别表示子数组（滑动窗口窗口）的开始位置和结束位置，维护变量 sum 存储子数组中的元素和（即从 nums[start] 到 nums[end] 的元素和）。

初始状态下，start 和 end 都指向下标 0，sum 的值为 0。

每一轮迭代，将 nums[end] 加到 sum，如果 sum≥s，则更新子数组的最小长度（此时子数组的长度是 end−start+1），然后将 nums[start] 从 sum 中减去并将 start 右移，直到 sum<s，在此过程中同样更新子数组的最小长度。在每一轮迭代的最后，将 end 右移。

代码如下

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) 
    {
        int n = nums.size();
        if (n == 0) 
        {
            return 0;
        }
        int ans = INT_MAX;
        int start = 0, end = 0;
        int sum = 0;
        while (end < n) 
        {
            sum += nums[end];
            while (sum >= s) 
            {
                ans = min(ans, end - start + 1);
                sum -= nums[start];
                start++;
            }
            end++;
        }
        return ans == INT_MAX ? 0 : ans;
    }
};

该方法时间复杂度：O(n)

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

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

class Solution
{
public:
 int longestOnes(vector<int>& nums, int k) 
 {
 int ret = 0;
 for(int left = 0, right = 0, zero = 0; right < nums.size(); right++)
 {
 if(nums[right] == 0) zero++; // 进窗⼝
 while(zero > k) // 判断
 if(nums[left++] == 0) zero--; // 出窗⼝
 ret = max(ret, right - left + 1); // 更新结果
 }
 return ret;
 }
};