滑动窗口例题

一、209:长度最小的子数组

209:长度最小的子数组

思路：1、暴力解法：两层for循环遍历，当sum >= target时计算子数组长度并与result比较，取最小的更新result。提交但是超出了时间限制。

class Solution {public int minSubArrayLen(int target, int[] nums) {int result = Integer.MAX_VALUE;int sum = 0;for (int i = 0; i < nums.length; i++) {sum = 0;for (int j = i; j < nums.length; j++) {sum += nums[j];if (sum >= target) {result = Math.min(j-i+1, result);break;}}}return result == Integer.MAX_VALUE ? 0 : result;}
}

        2、滑动窗口：所谓滑动窗口，就是不断的调节子序列的起始位置和终止位置，从而得出我们要想的结果。在暴力解法中，是一个for循环滑动窗口的起始位置，一个for循环为滑动窗口的终止位置，用两个for循环 完成了一个不断搜索区间的过程。

        只用一个for循环，那么这个循环的索引，一定是表示 滑动窗口的终止位置。滑动窗口也可以理解为双指针法的一种！只不过这种解法更像是一个窗口的移动，所以叫做滑动窗口更适合一些。

​

        for循环滑动窗口的终止位置，不断更新窗口的起始位置，因为窗口里面有多个符合大于target的窗口，比如第一个元素如果是负数，去掉之后还是大于target，所以循环里面的判断条件使用while而不使用if。

        不要以为for里放一个while就以为是O(n^2)， 主要是看每一个元素被操作的次数，每个元素在滑动窗后进来操作一次，出去操作一次，每个元素都是被操作两次，所以时间复杂度是 2 × n 也就是O(n)。

class Solution {public int minSubArrayLen(int target, int[] nums) {int left = 0;int sum = 0;int result = Integer.MAX_VALUE;for (int right = 0; right < nums.length; right++) {sum += nums[right];while (sum >= target) {result = Math.min(right-left+1, result);sum -= nums[left++];//这里体现滑动窗口的精髓，不断变更i(子序列的起始位置)}}return result == Integer.MAX_VALUE ? 0 : result;}
}

二、904.水果成篮

力扣

也是滑动窗口的题目。

class Solution {public int totalFruit(int[] fruits) {// 我们发现形成窗口大小其实是固定的(两个篮子==果子种类)// 键为果子类型，值为果子数量Map<Integer, Integer> map=new HashMap<>();int left = 0;int result = 0;for(int right = 0; right < fruits.length; right++) {map.put(fruits[right], map.getOrDefault(fruits[right], 0) + 1);// 窗口果子种类超过两种果子了，广快弄掉一个种类的果子while(map.size() > 2){map.put(fruits[left], map.get(fruits[left]) - 1);if(map.get(fruits[left]) == 0){map.remove(fruits[left]);}left++;}result = Math.max(result, right - left + 1);}return result;}
}

三、无重复的最长字串

无重复字符的最长子串https://leetcode.cn/problems/longest-substring-without-repeating-characters/

class Solution {public int lengthOfLongestSubstring(String s) {int len = s.length();int res = 0;int left = 0;Map<Character,Integer> map = new HashMap<>();for(int right = 0; right < len; right++) {if(map.containsKey(s.charAt(right))) {left = Math.max(left, map.get(s.charAt(right)) + 1);res = Math.max(res, right - left + 1);}map.put(s.charAt(right), right);}return res;}
}