公司建网,网站建设seo网络推广,网页制作是干什么的,重庆装修公司前十强大家好我是苏麟 , 今天带来滑动窗口经典的一些题目 . 我们继续来研究一些热门的、高频的滑动窗口问题 大纲 最长子串专题无重复字符的最长子串 长度最小的子数组盛最多水的容器 最长子串专题
无重复字符的最长子串
描述 :
给定一个字符串 s #xff0c;请你找出其中不含有重…大家好我是苏麟 , 今天带来滑动窗口经典的一些题目 . 我们继续来研究一些热门的、高频的滑动窗口问题 大纲 最长子串专题无重复字符的最长子串 长度最小的子数组盛最多水的容器 最长子串专题
无重复字符的最长子串
描述 :
给定一个字符串 s 请你找出其中不含有重复字符的 最长子串 的长度。
题目 :
LeetCode 3. 无重复字符的最长子串 :
无重复字符的最长子串
分析 :
官方题解
解析 :
class Solution {public int lengthOfLongestSubstring(String s) {if(s null || s.length() 0){return 0;}HashMapCharacter,Integer map new HashMap();int left 0;int max 0;for(int right 0;right s.length();right){if(map.containsKey(s.charAt(right))){left Math.max(left,map.get(s.charAt(right)) 1);}map.put(s.charAt(right),right);max Math.max(max,right - left 1);}return max;}
}长度最小的子数组
描述 :
给定一个含有 n 个正整数的数组和一个正整数 target 。
找出该数组中满足其总和大于等于 target 的长度最小的 连续子数组 [numsl, numsl1, …, numsr-1, numsr] 并返回其长度。如果不存在符合条件的子数组返回 0 。
题目 :
LeetCode 209. 长度最小的子数组 :
长度最小的子数组 分析 :
这题直接用双指针就完事了 , 没什么好说的 .
当然用队列啊 也是可以的 .
解析 :
class Solution {public int minSubArrayLen(int target, int[] nums) {int length nums.length - 1;int left 0;int right 0;int res 0;int min Integer.MAX_VALUE;while(right length){res nums[right];while(res target){res - nums[left];min Math.min(min, right - left 1);}}return min Integer.MAX_VALUE ? 0 : min;}
}盛最多水的容器
描述 :
给定一个长度为 n 的整数数组 height 。有 n 条垂线第 i 条线的两个端点是 (i, 0) 和 (i, height[i])
找出其中的两条线使得它们与 x 轴共同构成的容器可以容纳最多的水。
返回容器可以储存的最大水量。
说明你不能倾斜容器。
题目 :
LeetCode 11. 盛最多水的容器 :
盛最多水的容器
分析 :
本题看似复杂但其实简单的很。设两指针ij指向的水槽板高度分别为 h[i],h[j]此状态下水槽面积为S(i,j)。由于可容纳水的高度由两板中的 短板 决定因此可得如下面积公式:
s(i,j)min(h[i],h[j]) x ( j - i )
在每个状态下无论长板或短板向中间收窄一格都会导致水槽底边宽度-1 变短:
若向内移动短板水槽的短板min(h[i],h[j]) 可能变大因此下个水槽的面积可能增大若向内移动长板水槽的短板min(h[i],h[j]) 不变或变小因此下个水槽的面积一定变小。
因此只要初始化双指针分列水槽左右两端循环每轮将短板向内移动一格并更新面积最大值直到两指针相遇时跳出;即可获得最大面积。
解析 :
class Solution {public int maxArea(int[] height) {if(height.length 2){return 0;}int res 0;int left 0;int right height.length - 1;while(left right){res height[left] height[right] ?Math.max(res,(right - left) * height[left]) :Math.max(res,(right - left) * height[right--]);} return res;}
}这期就到这里 , 下期见!
