【滑动窗口】长度最小的子数组|无重复字符的最长子串|最大连续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

相关文章

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::

C++初始化数组的几种常见方法(简单易懂)

《C++初始化数组的几种常见方法(简单易懂)》本文介绍了C++中数组的初始化方法,包括一维数组和二维数组的初始化,以及用new动态初始化数组,在C++11及以上版本中,还提供了使用std::array... 目录1、初始化一维数组1.1、使用列表初始化(推荐方式)1.2、初始化部分列表1.3、使用std::

C++ Primer 多维数组的使用

《C++Primer多维数组的使用》本文主要介绍了多维数组在C++语言中的定义、初始化、下标引用以及使用范围for语句处理多维数组的方法,具有一定的参考价值,感兴趣的可以了解一下... 目录多维数组多维数组的初始化多维数组的下标引用使用范围for语句处理多维数组指针和多维数组多维数组严格来说,C++语言没

最长公共子序列问题的深度分析与Java实现方式

《最长公共子序列问题的深度分析与Java实现方式》本文详细介绍了最长公共子序列(LCS)问题,包括其概念、暴力解法、动态规划解法,并提供了Java代码实现,暴力解法虽然简单,但在大数据处理中效率较低,... 目录最长公共子序列问题概述问题理解与示例分析暴力解法思路与示例代码动态规划解法DP 表的构建与意义动

关于最长递增子序列问题概述

《关于最长递增子序列问题概述》本文详细介绍了最长递增子序列问题的定义及两种优化解法:贪心+二分查找和动态规划+状态压缩,贪心+二分查找时间复杂度为O(nlogn),通过维护一个有序的“尾巴”数组来高效... 一、最长递增子序列问题概述1. 问题定义给定一个整数序列,例如 nums = [10, 9, 2

Redis 多规则限流和防重复提交方案实现小结

《Redis多规则限流和防重复提交方案实现小结》本文主要介绍了Redis多规则限流和防重复提交方案实现小结,包括使用String结构和Zset结构来记录用户IP的访问次数,具有一定的参考价值,感兴趣... 目录一:使用 String 结构记录固定时间段内某用户 IP 访问某接口的次数二:使用 Zset 进行