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

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

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

最长子串专题

无重复字符的最长子串

描述 :

给定一个字符串 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;
    }
}

这期就到这里 , 下期见!