一、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;
}
}
