当前位置：首页 > news >正文

算法2：滑动窗口(上）

news 来源：原创 2024/7/5 20:24:42

文章目录

长度最小子数组
无重复字符的最长子串
[最大连续 1 的个数III](https://leetcode.cn/problems/max-consecutive-ones-iii/description/)
将x减到0的最小操作数

长度最小子数组

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int len = INT_MAX;int right = 0, left = 0;int sum = 0;while(left <= right && right < nums.size()){sum += nums[right++];//进窗口while(sum >= target) //判断{len = min(len, right - left);sum -= nums[left++]; // 出窗口}}return len == INT_MAX ? 0 : len;}
};

无重复字符的最长子串

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();int left = 0, right = 0;int hash[127] = {0};int res = 0;while (right < n) {hash[s[right]]++; // 进窗口，右端滑动if (hash[s[right]] > 1) {while (hash[s[left]] != hash[s[right]])hash[s[left++]]--;hash[s[left++]]--;} else {res = max(res, right - left + 1);}right++;}return res;}
};


int max(int a, int b)
{return a > b ? a : b;
}
int lengthOfLongestSubstring(char * s){int n = strlen(s);int left = 0, right = 0, res = 0;int hash[127] = {0};while(right < n){hash[s[right]]++;while(hash[s[right]] > 1)hash[s[left++]]--;res = max(res,right - left + 1);right++;}return res;
}

解析：

最大连续 1 的个数III

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int res = 0,zero = 0;for(int left = 0,right = 0; right < nums.size();right++){if(nums[right] == 0)    zero++;//进窗口while(zero > k){if(nums[left++] == 0) zero--;}    res = max(res,right - left + 1);}return res;}
};

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0, right = 0;int zero = 0, res = 0;while (right < nums.size()) {// 进窗口while (right < nums.size() && nums[right])right++;// 判断if (right < nums.size() && ++zero <= k) {right++;// 数据更新res = max(res, right - left);} else {// 数据更新res = max(res, right - left);// 出窗口while (left < right && nums[left])left++;k--;left++;right++;}}return res;}
};

将x减到0的最小操作数

正难则反

该题从正面去解，一会儿左一会儿右全凭场景所变化，编码写起来非常繁琐；此时，运用数学思维反证法来解决会不会简单些呢？该题需要求最小操作数，那也就意味着剩下的数据量是最大的，而且因为每次操作都在最左或者最右边，那也就是说剩下的数据是原数据的连续子串;OK，现在我们只需要求出一个符合的尽可能保证数据量大且其sum值等于sum(nums) - x 的连续子串即可.

那现在将符合要求数据看成一个窗口往后滑动即可。

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0;for(int e : nums)   sum += e;if(x > sum) return -1;if(x == sum) return nums.size();int target = sum - x;int res = -1;for(int left = 0, right = 0, tmp = 0; right < nums.size(); right++){tmp += nums[right];//进窗口while(tmp >= target){if(tmp == target)   res = max(res, right - left +1);//判断+记录长度tmp -= nums[left++];// 出窗口}}if(res == -1)return res;return nums.size() - res;}
};

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = 0;for (int e : nums)sum += e;if (x > sum)return -1;//细节int target = sum - x;int res = -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)res = max(res, right - left + 1); // 更新数据}if (res == -1)return res;return nums.size() - res;}
};