leetcode——滑動視窗

滑動視窗解法

滑動視窗的大概思想如下：

可以通過兩個指針來辨別視窗的邊界。
視窗的長度是可以固定的，也可以是可變的，完全取決于求解的問題性質。
維護一個或者一組和視窗相關聯的狀态變量，能有效降低計算量和算法複雜度。

無重複字元的最長子串

連結出處: https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/
算法思想:什麼是滑動視窗？
- 其實就是一個隊列,比如例題中的 abcabcbb，進入這個隊列（視窗）為 abc 滿足題目要求，當再進入a，隊列變成了 abca，這時候不滿足要求。是以，我們要移動這個隊列！
- 如何移動？我們隻要把隊列的左邊的元素移出就行了，直到滿足題目要求！

(1)解法:

class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] last = new int[128];
        for(int i = 0; i < 128; i++) {
            last[i] = -1;
        }
        int res = 0;
        int start = 0; // 視窗開始位置
        int n = s.length();
        for(int i = 0; i < s.length(); i++) {
            int index = s.charAt(i);
            start = Math.max(start, last[index]);
            //last[index]代表上一次出現的位置，但是字元串内字元不能重複，是以要從上一次出現位置的下一個位置開始
            //last[index]的存在是為了使得視窗滑動到下一個位置
            res   = Math.max(res, i - start + 1);//目前字元串個數 = 資料末指針-視窗初始位置+1
            last[index] = i+1;//視窗的下一個位置指派
        }
        return res;
    }
}

長度最小的子數組

連結： https://leetcode-cn.com/problems/minimum-size-subarray-sum/
參考文檔: https://leetcode-cn.com/problems/minimum-size-subarray-sum/solution/javade-jie-fa-ji-bai-liao-9985de-yong-hu-by-sdwwld/ (1)解法

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

滑動視窗最大值

連結：https://leetcode-cn.com/problems/sliding-window-maximum/

(1)解法一：（不推薦）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        int length = nums.length;
        int i = 0,j = 0;
        int out = length-k+1;//外循環次數 
        int []arr = new int[out];
        for(i = 0; i<out ; i++){
            int max = Integer.MIN_VALUE;
            for(j = i; j<i+k ; j++){
                max = Math.max(max,nums[j]);
            }
            arr[i] = max;
        }
        return arr;
    }
}

最小覆寫子串

https://leetcode-cn.com/problems/minimum-window-substring/
參考文旦： https://leetcode-cn.com/problems/minimum-window-substring/solution/leetcode-76-zui-xiao-fu-gai-zi-chuan-cja-lmqz/

class Solution {
    public String minWindow(String s, String t) {
        HashMap<Character,Integer> hs = new HashMap<Character,Integer>();
        HashMap<Character,Integer> ht = new HashMap<Character,Integer>();
        for(int i = 0;i < t.length();i ++){
            ht.put(t.charAt(i),ht.getOrDefault(t.charAt(i), 0) + 1);
        }
        String ans = "";
        int len = 1000000, cnt = 0;  
        for(int i = 0,j = 0;i < s.length();i ++)
        {
            hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);
            if(ht.containsKey(s.charAt(i)) && hs.get(s.charAt(i)) <= ht.get(s.charAt(i))) cnt ++;
            while(j < i && (!ht.containsKey(s.charAt(j)) || hs.get(s.charAt(j)) > ht.get(s.charAt(j))))
            {
                int count = hs.get(s.charAt(j)) - 1;
                hs.put(s.charAt(j), count);
                j ++;
            }
            if(cnt == t.length() && i - j + 1 < len){
                len = i - j + 1;
                ans = s.substring(j,i + 1);
            }
        }
        return ans;
    }
}

删除有序數組中的重複項

連結(26)：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/

class Solution {
    public int removeDuplicates(int[] nums) {
        int n = nums.length;
        if(n == 0) return 0;
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                slow ++;
            }
            fast ++;
        }
        return slow;
    }
}