209. 长度最小的子数组
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的 连续 子数组，并返回其长度。如果不存在符合条件的子数组，返回 0。
示例：
输入：s = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
进阶：
如果你已经完成了 O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/minimum-size-subarray-sum
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
暴力解最大的问题是重复计算的问题
如果我们知道了 nums[i...j] 那么nums[i...j-1]就很容易得到了：nums[i...j]-nums[j]
image.png
如果 num[i...j]<s 则j++
image.png
如果num[i..j]> 则i--
image.png
public int minSubArrayLen(int s, int[] nums) {
int l = 0;
int r = -1;
int minLen = nums.length + 1;
int sum = 0;
//nums[l..r] 为我们的滑动窗口
while (l < nums.length) {
if (r < nums.length-1 && sum < s) {
r++;
sum += nums[r];
} else {
sum -= nums[l];
l++;
}
if (sum >= s) {
minLen = Math.min(minLen, r - l + 1);
}
}
//如果minLen 没有变化 还是nums.length+1 说明没有找到合适的
if (minLen == nums.length + 1) {
return 0;
}
return minLen;
}
3. 无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例 1:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题解
在一个字符串中寻找没有重复字母的最长子串
字符集？只有字母？数字+字母？ASCII?
大小写是否敏感
如果s[i..j] 中没有s[j+1] 则右侧j++
image.png
假如产生了重复字符
s[i..j] 中产生了重复字符串，则
image.png
image.png
如何记录重复字符？ freq[256]，这个数组索引中如果是0，则没有该字符，如果是1则包含该字符。
public int lengthOfLongestSubstring(String s) {
int[] freq=new int[256]; //统计出现的字符个数 默认是0
int l=0;
int r=-1; //构造 a[l...r]滑动窗口
int maxLen=0;
while (l<s.length()){
//右边界 不在freq 统计数组中
if(r+1<s.length()&&freq[s.charAt(r+1)]==0){
r++;
freq[s.charAt(r)]++;
}else {
//移动左边界 直到该重复字符 被清除
freq[s.charAt(l)]--;
l++;
}
maxLen=Math.max(maxLen,r-l+1);
}
return maxLen;
}
