购物网站开发教学视频,短信营销哪个平台好,国家疾控局,企业网站建设规划ppt1. 长度最小的子数组 - 力扣#xff08;LeetCode#xff09;
1.题目解析#xff1a; 2.算法原理
#xff08;1#xff09;方法一#xff1a;暴力列举出所有的子数组的和
时间复杂度#xff1a;O#xff08;n**2#xff09;#xff1a;枚举所有子数组O#xff08;…
1. 长度最小的子数组 - 力扣LeetCode
1.题目解析 2.算法原理
1方法一暴力列举出所有的子数组的和
时间复杂度On**2枚举所有子数组On**2
2方法二
利用单调性两个指针都不回退使用同向双指针其实就是滑动窗口来优化 那么滑动窗口过程是怎么样的 1left 0rght 0 2进窗口 3判断 并决定什么时候出窗口 (其中二三步是循环的 还有一步更新结果这一步可能在2也可能在3 以【231243】为例模拟这个过程 开始left和right都指向2第一个元素 然后开始进窗口rightright指向3sum从0变为2 然后进行判断如果sumtarget更新结果并出窗口也就是left如果sumtarget继续进窗口也就是right) 正确性验证 利用单调性规避了很多没有必要的枚举行为(也就是当 sumtarget时right不用继续 时间复杂度ON 最坏情况left和right都走到数组的最后也就是NN2N 3.代码实现
class Solution {public int minSubArrayLen(int target, int[] nums) {int sum 0;int ret Integer.MAX_VALUE;for(int left0,right0;rightnums.length;right) {sumnums[right];//进窗口while(sumtarget) {//判断ret Math.min(right-left1,ret);//更新结果sum-nums[left];left;}}//要考虑特殊情况不存在return retInteger.MAX_VALUE ? 0:ret;}
} 2. 无重复字符的最长子串 - 力扣LeetCode
1.题目解析 2.算法原理 方法一暴力枚举 哈希表判断字符是否重复出现 时间复杂度ON**2 方法二利用规律使用滑动窗口来解决问题 1left 0rght 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 left0,right0;rights.length();right) {//进窗口hash[ss[right]];while(hash[ss[right]]1) {//有重复字符//删除hash[ss[left]]--;//出窗口left;}//更新结果len Math.max(len,right-left1);}return len;}
} 3. 最大连续1的个数 III - 力扣LeetCode
1.题目解析
2.算法原理
问题转化找出最长的子数组0的个数不超过k个 方法一暴力枚举zero计数器 方法二在暴力的情况下不让right回退—滑动窗口 1left 0rght 0 2进窗口:right如果是1无视如果是0计数器1 3判断(zerok) 并决定什么时候出窗口(left计数器-1 4更新结果出窗口结束 3.代码实现
class Solution {public int longestOnes(int[] nums, int k) {int count0;int zero0;for(int left0,right0;rightnums.length;right) {//进窗口if(nums[right]0){zero;}while(zerok) {//判断0的个数超过k个//出窗口if(nums[left]0) {zero--;}left;}countMath.max(count,right-left1);}return count;}
} 1658. 将 x 减到 0 的最小操作数 - 力扣LeetCode
1.题目解析 2.算法原理 正难则反找出最长的子数组的长度len所有元素的和正好等于sum-xtarget那么最后求的就是n-len的最小值 1left 0rght 0 2进窗口—Sumnums[right] 3判断 Sumtarget(此处不应该有因为要等于不能出窗口 并决定什么时候出窗口—sum-nums[left] 4更新结果这个时候需要加上判断sumtarget 3.代码实现
class Solution {public int minOperations(int[] nums, int x) {int Sum0;for(int a:nums) Suma;int sum0;int target Sum-x;//处理细节if(target0) {return -1;}int ret-1;for(int left0,right0;rightnums.length;right) {//进窗口sumnums[right];//判断while(sumtarget) {//出窗口sum-nums[left];}//更新结果if(sumtarget) {retMath.max(right-left1,ret);}}return (ret-1)?(-1):(nums.length-ret);}
}
