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

本文主要是介绍【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

1. 长度最小的子数组 - 力扣(LeetCode)

1.题目解析:

2.算法原理

(1)方法一:暴力列举出所有的子数组的和

时间复杂度:O(n**2):枚举所有子数组O(n**2)

(2)方法二:

利用单调性(两个指针都不回退),使用"同向双指针"(其实就是滑动窗口)来优化

那么滑动窗口过程是怎么样的?

<1>left  = 0,rght  = 0

<2>进窗口

<3>判断 并决定什么时候出窗口

(其中二三步是循环的)

还有一步更新结果:这一步可能在<2>,也可能在<3>

以【2,3,1,2,4,3】为例模拟这个过程

开始left和right都指向2(第一个元素),

然后开始进窗口(right++),right指向3,sum从0变为2,

然后进行判断,如果sum>target,更新结果并出窗口(也就是left++);如果sum<=target,继续进窗口(也就是right++)

正确性验证:

利用单调性,规避了很多没有必要的枚举行为(也就是当 sum>target时,right不用继续++)

 时间复杂度:O(N)

最坏情况:left和right都走到数组的最后,也就是N+N=2N

3.代码实现

class Solution {public int minSubArrayLen(int target, int[] nums) {int sum = 0;int ret = Integer.MAX_VALUE;for(int left=0,right=0;right<nums.length;right++) {sum+=nums[right];//进窗口while(sum>=target) {//判断ret = Math.min(right-left+1,ret);//更新结果sum-=nums[left];left++;}}//要考虑特殊情况:不存在return ret==Integer.MAX_VALUE ? 0:ret;}
}

2. 无重复字符的最长子串 - 力扣(LeetCode)

1.题目解析:

2.算法原理

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

时间复杂度:O(N**2)

方法二:利用规律,使用滑动窗口来解决问题

<1>left  = 0,rght  = 0

<2>进窗口(right++)—>让字符进入哈希表

<3>判断(窗口内是否出现重复字符)

有重复字符就出窗口(left++),从哈希表中删除该字符,这个过程需要一直重复,直到left找到重复的字符

<4>更新结果:在出完窗口到没有重复字符后就统计结果

3.代码实现

class Solution {public int lengthOfLongestSubstring(String s) {char[] ss = s.toCharArray();//字符串转为字符数组int[] hash = new int[128]; //用数组模拟哈希表int len = 0;for(int left=0,right=0;right<s.length();right++) {//进窗口hash[ss[right]]++;while(hash[ss[right]]>1) {//有重复字符//删除hash[ss[left]]--;//出窗口left++;}//更新结果len = Math.max(len,right-left+1);}return len;}
}

3. 最大连续1的个数 III - 力扣(LeetCode)

1.题目解析:

2.算法原理:

问题转化:找出最长的子数组,0的个数不超过k个

方法一:暴力枚举+zero计数器

方法二:在暴力的情况下不让right回退—>滑动窗口

<1>left  = 0,rght  = 0

<2>进窗口:right++,如果是1,无视;如果是0,计数器+1

<3>判断(zero>k) 并决定什么时候出窗口(left++,计数器-1)

<4>更新结果:出窗口结束

3.代码实现:

class Solution {public int longestOnes(int[] nums, int k) {int count=0;int zero=0;for(int left=0,right=0;right<nums.length;right++) {//进窗口if(nums[right]==0){zero++;}while(zero>k) {//判断:0的个数超过k个//出窗口if(nums[left]==0) {zero--;}left++;}count=Math.max(count,right-left+1);}return count;}
}

1658. 将 x 减到 0 的最小操作数 - 力扣(LeetCode)

1.题目解析:

2.算法原理:

正难则反:找出最长的子数组的长度(len),所有元素的和正好等于sum-x(target),那么最后求的就是n-len的最小值

<1>left  = 0,rght  = 0

<2>进窗口—>Sum+=nums[right]

<3>判断 Sum>target(此处不应该有==,因为要等于不能出窗口)

并决定什么时候出窗口—>sum-=nums[left]

<4>更新结果:这个时候需要加上判断sum==target

3.代码实现:

class Solution {public int minOperations(int[] nums, int x) {int Sum=0;for(int a:nums) Sum+=a;int sum=0;int target = Sum-x;//处理细节if(target<0) {return -1;}int ret=-1;for(int left=0,right=0;right<nums.length;right++) {//进窗口sum+=nums[right];//判断while(sum>target) {//出窗口sum-=nums[left++];}//更新结果if(sum==target) {ret=Math.max(right-left+1,ret);}}return (ret==-1)?(-1):(nums.length-ret);}
}

这篇关于【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续1的个数 III|将 x 减到 0 的最小操作数的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/828821

相关文章

MySQL重复数据处理的七种高效方法

《MySQL重复数据处理的七种高效方法》你是不是也曾遇到过这样的烦恼:明明系统测试时一切正常,上线后却频频出现重复数据,大批量导数据时,总有那么几条不听话的记录导致整个事务莫名回滚,今天,我就跟大家分... 目录1. 重复数据插入问题分析1.1 问题本质1.2 常见场景图2. 基础解决方案:使用异常捕获3.

Java数组初始化的五种方式

《Java数组初始化的五种方式》数组是Java中最基础且常用的数据结构之一,其初始化方式多样且各具特点,本文详细讲解Java数组初始化的五种方式,分析其适用场景、优劣势对比及注意事项,帮助避免常见陷阱... 目录1. 静态初始化:简洁但固定代码示例核心特点适用场景注意事项2. 动态初始化:灵活但需手动管理代

C++中初始化二维数组的几种常见方法

《C++中初始化二维数组的几种常见方法》本文详细介绍了在C++中初始化二维数组的不同方式,包括静态初始化、循环、全部为零、部分初始化、std::array和std::vector,以及std::vec... 目录1. 静态初始化2. 使用循环初始化3. 全部初始化为零4. 部分初始化5. 使用 std::a

shell编程之函数与数组的使用详解

《shell编程之函数与数组的使用详解》:本文主要介绍shell编程之函数与数组的使用,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录shell函数函数的用法俩个数求和系统资源监控并报警函数函数变量的作用范围函数的参数递归函数shell数组获取数组的长度读取某下的

MySQL高级查询之JOIN、子查询、窗口函数实际案例

《MySQL高级查询之JOIN、子查询、窗口函数实际案例》:本文主要介绍MySQL高级查询之JOIN、子查询、窗口函数实际案例的相关资料,JOIN用于多表关联查询,子查询用于数据筛选和过滤,窗口函... 目录前言1. JOIN(连接查询)1.1 内连接(INNER JOIN)1.2 左连接(LEFT JOI

C++原地删除有序数组重复项的N种方法

《C++原地删除有序数组重复项的N种方法》给定一个排序数组,你需要在原地删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度,不要使用额外的数组空间,你必须在原地修改输入数组并在使用O(... 目录一、问题二、问题分析三、算法实现四、问题变体:最多保留两次五、分析和代码实现5.1、问题分析5.

C语言字符函数和字符串函数示例详解

《C语言字符函数和字符串函数示例详解》本文详细介绍了C语言中字符分类函数、字符转换函数及字符串操作函数的使用方法,并通过示例代码展示了如何实现这些功能,通过这些内容,读者可以深入理解并掌握C语言中的字... 目录一、字符分类函数二、字符转换函数三、strlen的使用和模拟实现3.1strlen函数3.2st

Java中数组转换为列表的两种实现方式(超简单)

《Java中数组转换为列表的两种实现方式(超简单)》本文介绍了在Java中将数组转换为列表的两种常见方法使用Arrays.asList和Java8的StreamAPI,Arrays.asList方法简... 目录1. 使用Java Collections框架(Arrays.asList)1.1 示例代码1.

C# string转unicode字符的实现

《C#string转unicode字符的实现》本文主要介绍了C#string转unicode字符的实现,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随... 目录1. 获取字符串中每个字符的 Unicode 值示例代码:输出:2. 将 Unicode 值格式化

C++一个数组赋值给另一个数组方式

《C++一个数组赋值给另一个数组方式》文章介绍了三种在C++中将一个数组赋值给另一个数组的方法:使用循环逐个元素赋值、使用标准库函数std::copy或std::memcpy以及使用标准库容器,每种方... 目录C++一个数组赋值给另一个数组循环遍历赋值使用标准库中的函数 std::copy 或 std::