算法|滑动窗口、螺旋矩阵

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

题目连接：https://leetcode.cn/problems/minimum-size-subarray-sum/
思路：使用滑动窗口思想，for内是索引是窗口的终止位置，slow是窗口的起始位置，当窗口内元素和大于target时，调整起始位置slow的向前，直到target < sum,注意这里调整使用while 而不是if

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

二、904. 水果成篮 ☆☆☆

题目连接：https://leetcode.cn/problems/fruit-into-baskets/
思路：本题统计数组中种类为2的最长长度 。使用for fast为滑动窗口的起始位置，slow为窗口的终止位置，使用hashmap统计窗口中的水果的种类，当种类大于2即hashmap.size() > 2 调整窗口的终止位置，直到==2，然后统计种类=2的最长的长度

class Solution {
    public int totalFruit(int[] fruits) {
        int slow = 0;
        int result = 0;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        for (int fast = 0; fast < fruits.length; fast++) {
            hashMap.put(fruits[fast], hashMap.getOrDefault(fruits[fast], 0) + 1);
            while (hashMap.size() > 2) {
                hashMap.put(fruits[slow], hashMap.get(fruits[slow]) - 1);
                if (hashMap.get(fruits[slow]) == 0) {
                    hashMap.remove(fruits[slow]);
                }
                slow++;
            }
            result = Math.max(result, fast - slow + 1);
        }
        return result;
    }
}

三、 76. 最小覆盖子串 ☆☆☆

题目连接：https://leetcode.cn/problems/minimum-window-substring/
思路：使用两个hashmap，当t的hashmap和s的hashmap中字符的数量相同时 个数count+1, 当s中的出现的个数和t的个数相同时，即是符合窗口的内条件，然后在循环内缩小窗口范围，返回最小长度的的左边界和长度。

class Solution {
    public String minWindow(String s, String t) {
        if (s == null || s.length() == 0) return "";
        if (t == null || t.length() == 0) return "";
        HashMap<Character, Integer> thashMap = new HashMap<>();
        for (int i = 0; i < t.length(); i++){
            thashMap.put(t.charAt(i), thashMap.getOrDefault(t.charAt(i), 0) + 1);
        } 
        
        int slow = 0;
        int count = 0;
        int minLength = Integer.MAX_VALUE;
        int left = 0;
        HashMap<Character, Integer> shashMap = new HashMap<>();
        
        for (int fast = 0; fast < s.length(); fast++){
            char c = s.charAt(fast);
            shashMap.put(c, shashMap.getOrDefault(c, 0) + 1);
            if (shashMap.get(c).equals(thashMap.getOrDefault(c, 0))){
                count++;
            }
            while (count == thashMap.size()){
                int length = fast - slow + 1;
                if (minLength > length) {
                    //更新;
                    minLength = length;
                    left = slow;
                }
                char cc = s.charAt(slow);
                if (shashMap.get(cc).equals(thashMap.getOrDefault(cc, 0))) {
                    count--;
                }
                shashMap.put(cc, shashMap.get(cc) - 1);
                slow++;
            }
        }
        System.out.println(minLength + " " + left);
        return minLength == Integer.MAX_VALUE ? "" : s.substring(left,  left + minLength);
       
    }
}

四、 59. 螺旋矩阵 II

题目连接：https://leetcode.cn/problems/spiral-matrix-ii/

思路：使用前闭后开的原则遍历，圈数= n / 2 如果是奇数中间的位置是(start, start) = count;
class Solution {
    public int[][] generateMatrix(int n) {
        int nums[][] = new int[n][n];
        int loop = 0;
        int start = 0;
        int count = 1;
        while (loop++ < n / 2){
            int j = start;
            for (;j < n - loop; j++){
                nums[start][j] = count++;
            }
            int i = start;
            for (; i < n - loop; i++){
                nums[i][j] = count++;
            }
            for (; j >= loop; j--){
                nums[i][j] = count++;
            }
            for (; i >= loop; i--) {
                nums[i][j] = count++;
            }
            start++;
        }
        if (n % 2 == 1) nums[start][start] = count;
        return nums;
    }
}