嗨，大家好，我是袁廚（因為酷愛做飯，所以自己考取了廚師證）。之前一直看大家寫的部落格，學到了很多東西。然後最近萌生了自己寫的想法，將自己知道的分享給需要的同學。以後每天會為大家分享leetcode精選題目的各種題解，並且每週會整理一下該周刷的所有題目，及解題框架。大家微信搜尋【程式設計師愛做飯】關注我吧！

---

209，長度最小的子陣列

• 題目描述
• 暴力解法
• • 做題思路
  • 題目程式碼
• 滑動視窗
• • 做題思路
  • 題目程式碼
• 總結

---

題目描述

---

暴力解法

做題思路

遇到這個題目的第一思路獲取就是滑動視窗了，但是我們目前還沒有學習滑動視窗，那我們可以先通過暴力解法解決呀，之前一個學長給我說，面試的時候不要管什麼方法，你只要把題目做出來，就是好方法，所以我們先想著解決這個問題，然後再進行優化。我的大致思路就是，通過兩層迴圈進行元素累加，第一個迴圈負責定位起點，然後從起點開始累加之後的元素，直到我們累加和大於等於目標值。然後保留當前子陣列的長度，更換下一起點，直到遍歷結束。

省略了綠指標移動過程

最後min的值為2，所以輸出2.時間複雜度O(n^2),空間複雜度O(1)

題目程式碼

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int sum = 0;//定義累加的變數
        int childlen = 0;//子陣列長度
        int minlen = Integer.MAX_VALUE;//int最大整數，常用
        for(int i = 0 ;i < nums.length ; i++){
            sum = 0;//每次都要歸0，因為起點更換
            for(int j = i;j < nums.length ;j++ ){
                sum += nums[j];
                //這裡是大於等於，我原來理解錯誤題目，寫的等於，浪費一次提交
                if(sum >= s){
                     //子孩子長度
                    childlen = j-i+1;
                    //最小值
                    minlen = Math.min(minlen,childlen);
                    break;
                }
            }
        }
        //這裡不可以直接返回minlen，因為有可能存在不存在子陣列的情況。
        return minlen==Integer.MAX_VALUE ? 0: minlen;
    }
}

 

---

 

滑動視窗

做題思路

滑動視窗是陣列操作中的一種重要方法，陣列中很多題目都可以通過滑動視窗來解決。暴力法中，我們的紅指標在一次迴圈中是不變的，綠指標進行移動，滑動視窗呢，就是通過不斷調節子陣列的起始位置和終止位置，進而得到我們想要的結果我們也可以看成是雙指標的一種。






紅指標和綠指標之間的距離就是滑動視窗的大小，符合條件的最小視窗大小為2，其實也很好理解這個思想，就是當紅綠之間的和符合條件時，就移動紅指標判斷是否仍符合條件，不符合就移動綠指標，並記錄最小的子長度，直到綠指標移動到最後。
時間複雜度O(n),空間複雜度O(1)

題目程式碼

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int chiledlen = Integer.MAX_VALUE;//子陣列長度
        int winlen = 0;//視窗大小
        int sum = 0;
        int i = 0;//起始長度位置
        for(int j = 0 ; j < nums.length;j++){
              sum += nums[j];
              //發現符合條件的情況
              while(sum>=s){
                  winlen = j-i+1;//視窗大小
                  chiledlen = Math.min(chiledlen,winlen);
                  //下面兩行是滑動視窗的意義所在，改變起點位置，判斷是否仍符合條件
                  sum-=nums[i];
                  i++;
              }

        }
        return chiledlen == Integer.MAX_VALUE ? 0:chiledlen;
    }
}

總結

這個題目是非常好的一個題，大家可以自己做一下，算是初探滑動視窗，大家有更好的方法可以評論討論啊。

更多題目總結請掃描下面二維條碼，一塊刷題呀。

作者：LeetCode
連結：https://leetcode-cn.com/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode/
來源：力扣（LeetCode）
著作權歸作者所有。商業轉載請聯絡作者獲得授權，非商業轉載請註明出處。