209. 长度最小的子数组 与 3. 无重复字符的最长子串

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