算法通关村第十六关-白银挑战滑动窗口经典题目

大家好我是苏麟 , 今天带来滑动窗口经典的一些题目 .

我们继续来研究一些热门的、高频的滑动窗口问题

最长子串专题

无重复字符的最长子串

描述 :

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

题目 :

LeetCode 3. 无重复字符的最长子串 :

无重复字符的最长子串

分析 :

官方题解

解析 :

class Solution {public int lengthOfLongestSubstring(String s) {if(s == null || s.length() == 0){return 0;}HashMap<Character,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, numsl+1, …, 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. 盛最多水的容器 :

盛最多水的容器

分析 :

本题看似复杂，但其实简单的很。设两指针i，j，指向的水槽板高度分别为 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;}
}

这期就到这里 , 下期见!