滑动窗口

406. 和大于S的最小子数组

描述
给定一个由 n 个正整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。

样例
给定数组 [2,3,1,2,4,3] 和 s = 7, 子数组 [4,3] 是该条件下的最小长度子数组。

挑战
如果你已经完成了O(n)时间复杂度的编程，请再试试 O(n log n)时间复杂度。

image.png

不懂的可以看看这个视频
https://www.bilibili.com/video/av24299540/?p=14

public class Solution {
    /**
     * @param nums: an array of integers
     * @param s: An integer
     * @return: an integer representing the minimum size of subarray
     */
    public int minimumSize(int[] nums, int s) {
        // 滑动窗口模型
        
        int left = 0;
        int right = -1;  // [left, right]表示窗口大小
        
        int res = Integer.MAX_VALUE;
        int sum = 0;
        
        while (left < nums.length) {
            if (right < nums.length - 1 && sum < s) {
                ++right;
                sum += nums[right];
            } else {
                sum -= nums[left];
                left++;
            }
            
            if (sum >= s) {
                res = Math.min(res, right - left + 1);
            }
        }
        
        return res == Integer.MAX_VALUE ? -1 : res;
    }
}

384. 最长无重复字符的子串

描述
给定一个字符串，请找出其中无重复字符的最长子字符串。

样例
例如，在"abcabcbb"中，其无重复字符的最长子字符串是"abc"，其长度为 3。

对于，"bbbbb"，其无重复字符的最长子字符串为"b"，长度为1。

挑战
O(n) 时间

https://www.bilibili.com/video/av24299540/?p=15

public class Solution {
    /**
     * @param s: a string
     * @return: an integer
     */
    public int lengthOfLongestSubstring(String s) {
        int[] f = new int[256];
        
        int left = 0;
        int right = -1;
        int res = 0;
        
        while (left < s.length()) {
            if (right < s.length() - 1 && f[s.charAt(right + 1)] == 0) {
                f[s.charAt(++right)] ++;
            } else {
                f[s.charAt(left++)]--;
            }
            
            res = Math.max(res, right - left + 1);
        }
        return res;
    }
}