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

目录

长度最小的子数组

解题思路

代码实现

无重复字符的最大字串

解题思路

代码实现

最大连续1的个数l l l

解题思路

代码实现

将x减到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 <= kwhile(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😴✨🎞