[Lc滑动窗口_1] 长度最小的数组 | 无重复字符的最长子串 | 最大连续1的个数 III | 将 x 减到 0 的最小操作数

目录

1. 长度最小的字数组

题解

代码

⭕2.无重复字符的最长子串

题解

代码

3.最大连续1的个数 III

题解

代码

4.将 x 减到 0 的最小操作数

题解

代码

1. 长度最小的字数组

题目链接：209.长度最小的字数组

题目分析:

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

找出该数组中满足其总和大于等于 target 的长度最小的 子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。

（子数组：是连续的！！！）

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

题解

  • 注意题目说的是 正整数 数组，说明数组里面的数是大于等于0的数。
  • 因此这道题我们有一种优化的方法。
  • 题目让找连续的子数组和>=target，并且长度最小。有很多种情况，但是我们选择的是 最小长度。

算法原理：

不管什么题，首先我们一定会先想到的是 暴力求解，因为只有暴力求解出来了，我们就可以在暴力求解的基础上进行优化~

解法一：暴力枚举出所有的子数组的和

两层for循环，O(N^2)

for(int i=0;i<n;i++)for(int j=i;j<n;j++)sum+=num[j];
//固定一个数，挨个往后加if(sum>=target)min(len,j-i+1)

注意到此时暴力枚举是有优化的。

题目说的是一个 正整数数组，都是大于等于0的数，这个 sum是呈现出递增的状态的，单调递增!

在暴力求解中，此时right还要++，但是注意题目本来要求的就是 最小长度

此时sum在加上往上走了一步的right的num[right]，一定是满足sum>=target，但是len变成5了，一定不会是最终结果

因此当条件已经满足sum>=target ，right就不用动了。right后面也就不用再枚举了。

那现在让 left+1，right和left指向同一下标，然后再重复上面过程，那有个问题，这段区间的和能不能直接算出来？

  • 当然可以。
  • 现在sum=8，我只需要把让sum减去num[left]，不就是现在left和right所在的区间和算出来吗。
  • 没有必要让right傻傻的回退然后重新加。因此right不动，更新sum=6.

因此我们从暴力枚举中发现两个优化：

  • 一个是right 满足后，后面不用枚举
  • 一个left++，right不用回退，

所以我们可以利用单调性，使用双指针优化。

解法二：利用单调性，使用 “同向双指针” 来优化

当我们在暴力枚举的策略中发现left和right都是从左向右一个方向移动，我们就称为这两个指针叫做同向指针。同向双指针又称为滑动窗口。

什么是滑动窗口？

本质上是 “同向双指针”，left从左到右移动，right不回退，从左到右移动，用left和right一直 维护这个区间的和，然后这两个指针从左向右移动的过程非常像一个窗口在这个数组里滑来滑去。

什么时候用滑动窗口？

利用单调性，用滑动窗口解决问题。

当我们发现在暴力求解时，两个指针都可以做到 不回退，都是向同一个方向移动的时候，此时就可以用滑动窗口。

滑动窗口怎么用？

  1. 初始left=0，right=0，充当窗口左端点，右端点。用left，right标记窗口左区间，右区间。
  2. 右窗口（++right）（右值进窗口）
  3. 判断
    • 根据判断决定是否 左窗口(++left)（左值出窗口）
  1. 更新结果
    • 2，3都有可能会更新结果，看题目要求

左窗口，判断，右窗口一直循环，直到right 超过区间长度结束，更新结果看题目要求(右窗口，左窗口都有可能)，。

滑动窗口正确性

  • 暴力枚举肯定对的，因为已经把所有子数组的情况都找出来了。
  • 虽然滑动窗口并没有把没有把所有情况都枚举出来，但是这里利用单调性，规避了没有必要的枚举
  • 虽然没有把所有情况真正枚举出来，但是已经判断出有些子数组不是最终结果，已经把所有结果都考虑进来了，所以这种策略是跟暴力枚举是一样正确的。

滑动窗口时间复杂度

进窗口是一个循环，判断也是一个循环。

两层循环套在一起。可能会觉得时间复杂度O(N^2)，但是不能看代码算时间复杂度，要看实际情况分析实际复杂度。

实际我们只会让right向前移动，left也向前移动，即使时最坏情况，right移动到最后一个元素，left 也移动到最后一个元素，因为单调性，总共也就操作了 n+n=2n 次 整体时间复杂度O(N)。

代码

要考虑到，栈溢出（heap-buffer-overflow） 的边界情况

可详见前文

在Leetcode中，无穷大和无穷小分别怎么表示

C/C++中可以使用INT_MAX和INT_MIN

⭕2.无重复字符的最长子串

题目链接：3. 无重复字符的最长子串

题目分析:

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

子串和子数组都是连续的

❗❗❗ 模拟分析示例：

题解

算法原理：

首先还是暴力枚举，然后根据暴力枚举进行优化。

  • 以下面为例，两层for循环，但是下面找到的结果都是我们站在上帝角度，编译器并不知到什么时候结束。
  • 一般对应判断是否有重复元素，我们都可以用哈希表来解决问题。
  • 使用哈希表，判断是否有重复元素，比如让你判断一个数组是否有重复，或者两个数组是否有重复都可以用哈希映射！

解法一：暴力枚举+哈希表(判断字符是否重复出现)

O(N^2)

根据解法一做优化，定义一个left，right指针。当right走到有重复的元素后，已经找到一个字串，其中left到right区间每个元素都已经进入hash表。

此时left向前走一步，但是这个区间还是有重复元素，因此left要走到没有重复的区间才行，

然后这个时候以前做法是right回退然后重新往下走，但是这里left到right区间元素本来就在hash表里

因此就不需要right回退了，而是向right继续向前走。然后重复上面过程，直到right走到结尾。结束~

这不就是滑动窗口的思想吗。双向指针，left往前走，right不回退一直往前走

解法二：利用规律，使用 “滑动窗口” 解决问题

  1. left=0，right=0
  2. 进窗口
  3. 判断
    • 出窗口
  1. 更新结果

进窗口、判断、出窗口，更新结果是一个大循环过程。直到right到结尾循环结束。

其中判断、出窗口是一个小循环（直到跳出重复字符）。不过时间复杂度还是O(N).

注意：

  • 更新结果可能在  进窗口后，判断后，出窗口后，判断后任意一个地方，看题目要求

本题：

  • 进窗口 ->-> 让字符进入哈希表
  • 判断-> 窗口内出现重复元素
  • 出窗口-> 从哈希表中删除该字符

代码

class Solution {
public:int lengthOfLongestSubstring(string s) {//！！if(s.empty()) return 0; // 处理空输入vector<char> str;for(char c:s) str.push_back(c);int left=0,right=0,n=str.size(),len=0;//unordered_set ret;unordered_set<char> ret;while(right<n){
//先检查while(ret.count(str[right])){ret.erase(str[left]);left++;//利用了连续性//表中 发现了右元素已存在//要在左边 进行跳过}
//不存在 就插入ret.insert(str[right]);len=max(len,right-left+1);right++;}return len;}
};

总结一下：

利用单调性，使用 双指针 解决问题。

  • 一般left和right，一个指向数组最左边，一个指向数组最右边，然后一次可以排除一批，再然后left++，–right，两个指针是对撞的。

这里利用单调性或者利用规律，使用 滑动窗口 解决问题

  • 滑动窗口也使用双指针解决问题，不过left一直从前往后走，right不回退从前往后走，两个指针是同向的。因此滑动窗口本质其实是 同向双指针。

3.最大连续1的个数 III

题目链接：1004. 最大连续1的个数 III

题目分析:

给定一个二进制数组 nums 和一个整数 k，假设最多可以翻转 k 个 0 ，则返回执行操作后 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

题解

题目说的翻转实际上是把0变成1的意思，最多翻转K次，说明小于等于K都是可以的。

拿到题我们开始肯定想的是暴力求解。

如果直接暴力求解，遇到0->1了，那下一次在遍历就有问题了。

因此我们换一个思路。这道题不是让转化后最大连续1的个数吗。

我们转化为：找出最长的子数组，数组里0的个数不超过K个，这个数组里面0一定能够转化成1。

算法原理：

解法一：暴力枚举+zero计数器

伪代码，两层for循环，统计zero的个数，满足zero>k，统计此时数组长度，然后重新进入循环，注意每次zero都清0

for(int i=0;i<n;++i)for(int j=i;j<n;++j)//双指针 查找出一段区间if(nums[j]==0)++zero;if(zero>k)ret=max(ret,right-left+1)

然后我们根据暴力枚举，看看有没有优化的可能。

定义两个指针left，right，right走到zero>k的位置，zero=3，大于k。

按照暴力求解left++，然后right回溯然后重新往后走。但是我们发现没有必要，现在left往前走一步，你会发现，right还是停留在老位置，这个区间不用在管的，直接丢弃。

因此，让left一直走到zero<=k的位置。然后 right也根本不用回溯 然后在重新走，而是直接往后走就行了。

根据上面的发现，当在暴力枚举中，发现left，right是同向移动的，利用这个规律，使用滑动窗口解决问题

解法二：利用规律，使用滑动窗口

  1. left=0，right=0
  2. 进窗口
  3. 判断
    • 出窗口
  1. 更新结果

进窗口 -> 如果是1，不理会。如果是0，计数器+1

判断 -> zero>k

出窗口 -> 如果是1，不理会。如果是0，计数器-1

更新结果：在判断之后在更新

代码

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

4.将 x 减到 0 的最小操作数

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

题目分析:

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

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

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

题解

这道题让每次从数组左右两边移除一个数，然后就是一个新的数组，然后再从新的数组再从左右两边移除一个数。

  • 但是如果真的硬着头皮开始做，其实是很困难的。
  • 并不知道每次是从最左边走还是最右边找。有可能这次左边下次右边或者还是左边，情况太复杂了。

因此我们可以利用 正难则反 的思想

  • 正对面解题太难，那就想对立面，换个思路。
  • 不是每次从左右两端找一个数吗，那可能找到情况就是a+b=x，a、b什么情况都要，但是中间这个连续区间的和不也是确定的吗sum-x
  • 也就是这道题我们转换成，找出最长的子数组长度，所有元素的和正好等于sum-x，然后数组总长减去这段子区间长度不就是问题答案吗
  • 如果没找到说明这个数组不存在将x减到0的数，直接返回-1

解法一：暴力求解

初始left，right指向同一下标，当right走到和大于target的时候，left往前走

按照暴力求解，right要回到和left相同下标，然后right在重新往前走，直到再次走到和大于target的地方停下来，然后重复上面过程。

  • 但是今天这里不需要right回溯，因为right回溯后重新走到下面的位置，因为left已经往前走了，这段区间的和肯定是更小了
  • 因此就不需要right回溯了。要么right不动，要么right往后走。
  • 同向双指针 ----> 本质就是滑动窗口

解法二：使用滑动窗口

代码


class Solution {
public:
int minOperations(vector<int>& nums, int x)
{if(nums.empty()) return -1;int sum=0;for(auto c:nums)sum+=c;// 新增边界条件处理if (sum == x) return nums.size();  // 整个数组和正好等于xif (sum < x) return -1;            // 总和不足，无法达成目标int target=sum-x,len=0;int left=0,right=0,n=nums.size(),add=0;while(right<n){add+=nums[right];while(add>target){add-=nums[left];left++;}if(add==target)len=max(len,right-left+1);right++;}//！！！len>0      return (len > 0) ? (nums.size() - len) : -1;
}
};

测试样例跑不全时，要注意对 边界情况 的处理

  • 若不存在这样的子数组（len = 0）

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/26807.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

MySQL 事务笔记

MySQL 事务笔记

MySQL 事务笔记 目录 事务简介事务操作事务四大特性并发事务问题事务隔离级别总结 事务简介 事务&#xff08;Transaction&#xff09;是数据库操作的逻辑单元&#xff0c;由一组不可分割的SQL操作组成。主要用于保证&#xff1a; 多个操作的原子性&#xff08;要么全部成功…
阅读更多...
数据结构秘籍（四） 堆 （详细包含用途、分类、存储、操作等）

数据结构秘籍（四） 堆 （详细包含用途、分类、存储、操作等）

1 引言 什么是堆&#xff1f; 堆是一种满足以下条件的树&#xff1a;&#xff08;树这一篇可以参考我的文章数据结构秘籍&#xff08;三&#xff09;树 &#xff08;含二叉树的分类、存储和定义&#xff09;-CSDN博客&#xff09; 堆中的每一个结点值都大于等于&#xff08…
阅读更多...
【网络安全 | 渗透测试】GraphQL精讲一：基础知识

【网络安全 | 渗透测试】GraphQL精讲一：基础知识

未经许可，不得转载， 文章目录 GraphQL 定义GraphQL 工作原理GraphQL 模式GraphQL 查询GraphQL 变更（Mutations）查询（Queries）和变更（Mutations）的组成部分字段（Fields）参数（Arguments）变量别名（Aliases）片段（Fragments）订阅（Subscriptions）自省（Introspecti…
阅读更多...
EMQX中不同端口对应的接入协议

EMQX中不同端口对应的接入协议

使用tcp接入时应使用mqtt://IP:1883 使用ws接入时应使用ws://IP:8083
阅读更多...
2020年蓝桥杯Java B组第二场题目+部分个人解析

2020年蓝桥杯Java B组第二场题目+部分个人解析

#A&#xff1a;门牌制作 624 解一&#xff1a; public static void main(String[] args) {int count0;for(int i1;i<2020;i) {int ni;while(n>0) {if(n%102) {count;}n/10;}}System.out.println(count);} 解二&#xff1a; public static void main(String[] args) {…
阅读更多...
数据结构：反射 和 枚举

数据结构：反射 和 枚举

目录 一、反射 1、定义 2、反射相关的类 3、Class类 &#xff08;2&#xff09;常用获得类中属性相关的方法&#xff1a; &#xff08;3&#xff09;获得类中注解相关的方法&#xff1a; &#xff08;4&#xff09;获得类中构造器相关的方法&#xff1a; &#xff08;…
阅读更多...
QT-对象树

QT-对象树

思维导图 写1个Widget窗口&#xff0c;窗口里面放1个按钮&#xff0c;按钮随便叫什么 创建2个Widget对象 Widget w1,w2 w1.show() w2不管 要求&#xff1a;点击 w1.btn ,w1隐藏&#xff0c;w2显示 点击 w2.btn ,w2隐藏&#xff0c;w1 显示 #include <QApplication> #inc…
阅读更多...
LLMs之DeepSeek：DeepSeek-V3/R1推理系统的架构设计和性能统计的简介、细节分析之详细攻略

LLMs之DeepSeek：DeepSeek-V3/R1推理系统的架构设计和性能统计的简介、细节分析之详细攻略

LLMs之DeepSeek&#xff1a;DeepSeek-V3/R1推理系统的架构设计和性能统计的简介、细节分析之详细攻略 目录 DeepSeek-V3/R1推理系统的架构设计 1、大规模跨节点专家并行 (EP) 2、计算-通信重叠 3、负载均衡 4、在线推理系统图 DeepSeek-V3/R1推理系统的架构设计 2025年3月…
阅读更多...
开启AI短剧新纪元!SkyReels-V1/A1双剑合璧!昆仑万维开源首个面向AI短剧的视频生成模型

开启AI短剧新纪元!SkyReels-V1/A1双剑合璧!昆仑万维开源首个面向AI短剧的视频生成模型

论文链接&#xff1a;https://arxiv.org/abs/2502.10841 项目链接&#xff1a;https://skyworkai.github.io/skyreels-a1.github.io/ Demo链接&#xff1a;https://www.skyreels.ai/ 开源地址&#xff1a;https://github.com/SkyworkAI/SkyReels-A1 https://github.com/Skywork…
阅读更多...
苹果廉价机型 iPhone 16e 影像系统深度解析

苹果廉价机型 iPhone 16e 影像系统深度解析

【人像拍摄差异】 尽管iPhone 16e支持后期焦点调整功能&#xff0c;但用户无法像iPhone 16系列那样通过点击屏幕实时切换拍摄主体。前置摄像头同样缺失人像深度控制功能&#xff0c;不过TrueTone原彩闪光灯系统在前后摄均有保留。 很多人都高估了 iPhone 的安全性&#xff0c;查…
阅读更多...
中科大计算机网络原理 1.5 Internt结构和ISP

中科大计算机网络原理 1.5 Internt结构和ISP

一、互联网的层次化架构 ‌覆盖范围分层‌ ‌主干网&#xff08;Tier-1级&#xff09;‌ 国家级或行业级核心网络&#xff0c;承担跨区域数据传输和全球互联功能。例如中国的四大主干网&#xff08;ChinaNET、CERNET等&#xff09;以及跨国运营商&#xff08;如AT&T、Deuts…
阅读更多...
线程 -- 线程池

线程 -- 线程池

线程池 谈起线程池之前&#xff0c;我们可以联想到常量池&#xff0c;那什么是常量池呢&#xff1f; 常量池&#xff1a;字符串常量&#xff0c;在 Java 程序最初构建的时候&#xff0c;就已经准备好了。等程序运行的时候&#xff0c;这样的常量也就加载到内存中了。因此剩下…
阅读更多...
uniapp-原生android插件开发摘要

uniapp-原生android插件开发摘要

uni-app在App侧的原生扩展插件&#xff0c;支持使用java、object-c等原生语言编写&#xff0c;从HBuilderX 3.6起&#xff0c;新增支持了使用uts来开发原生插件。 基础项目 UniPlugin-Hello-AS工程请在App离线SDK中查找 基础项目(App离线SDK)已经配置好了自定义插件所需要的…
阅读更多...
Hive-05之查询 分组、排序、case when、 什么情况下Hive可以避免进行MapReduce

Hive-05之查询 分组、排序、case when、 什么情况下Hive可以避免进行MapReduce

一、目标 掌握hive中select查询语句中的基本语法掌握hive中select查询语句的分组掌握hive中select查询语句中的join掌握hive中select查询语句中的排序 二、要点 1. 基本查询 注意 SQL 语言大小写不敏感SQL 可以写在一行或者多行关键字不能被缩写也不能分行各子句一般要分行…
阅读更多...
MacDroid for Mac v2.3 安卓手机文件传输助手 支持M、Intel芯片 4.7K

MacDroid for Mac v2.3 安卓手机文件传输助手 支持M、Intel芯片 4.7K

MacDroid 是Mac毒搜集到的一款安卓手机文件传输助手&#xff0c;在Mac和Android设备之间传输文件。您只需要将安卓手机使用 USB 连接到 Mac 电脑上即可将安卓设备挂载为本地磁盘&#xff0c;就像编辑mac磁盘上的文件一样编辑安卓设备上的文件&#xff0c;MacDroid支持所有 Andr…
阅读更多...
题解：洛谷 P2199 最后的迷宫

题解：洛谷 P2199 最后的迷宫

题目https://www.luogu.com.cn/problem/P2199 显然&#xff0c;数据最大 &#xff0c;数组我们开不下&#xff0c;动态开数组。 对于每一个查询&#xff0c;从起点开始&#xff0c;走一步判断是否能看到火焰杯。 如果已经没法走了&#xff0c;直接拆墙&#xff0c;输出 Poor…
阅读更多...
如何在Github上面上传本地文件夹

如何在Github上面上传本地文件夹

前言 直接在GitHub网址上面上传文件夹是不行的&#xff0c;需要一层一层创建然后上传&#xff0c;而且文件的大小也有限制&#xff0c;使用Git进行上传更加方便和实用 1.下载和安装Git Git - Downloads 傻瓜式安装即可 2.获取密钥对 打开自己的Github&#xff0c;创建SSH密钥&…
阅读更多...
vscode接入ai插件（免费版）

vscode接入ai插件（免费版）

一、安装插件 扩展程序搜索tongyilingma 点击install安装 二、登录阿里云 安装好之后左侧会出现通义的图标。 点击通义图标&#xff0c;右上角登录。 登陆成功后即可使用。 三、位置 在左边可能不太符合编码习惯&#xff0c;我们点击右侧位置图标&#xff0c;把通义图标拖…
阅读更多...
【deepseek第二课】docker部署dify，配置私有化知识库，解决网络超时，成功安装

【deepseek第二课】docker部署dify，配置私有化知识库，解决网络超时，成功安装

【deepseek第二课】docker部署dify，配置私有化知识库，解决网络超时，成功安装 1. dify安装1.1 官网安装文档介绍1.2 安装报错，网络连接问题使用镜像加速器处理1.3 dify后台启动很多docker进程2. 页面探索2.1 设置管理账号2.2 添加ollama支持的模型3. 创建知识库4. 创建一个聊…
阅读更多...
如何利用SpringSecurity进行认证与授权

如何利用SpringSecurity进行认证与授权

目录 一、SpringSecurity简介 1.1 入门Demo 二、认证 ?编辑 2.1 SpringSecurity完整流程 2.2 认证流程详解 ?2.3 自定义认证实现 2.3.1 数据库校验用户 2.3.2 密码加密存储 2.3.3 登录接口实现 2.3.4 认证过滤器 2.3.5 退出登录? 三、授权 3.1 权限系统作用 …
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023