算法訓練|滑動視窗

模式一:滑動視窗

模式說明：輸入一個數組或者字元串。求解的結果是具有某種特質的子數組或者子字元串。這種情況下，可以使用滑動視窗的方法求解。

其中，滑動視窗是一個大小不固定的一個數組，最重要的就是判斷這個數組的起始指針和結束指針如何移動。

從上面這道題來看的話，如果滿足條件，幹掉左指針，即左指針向右移動一位，不滿足條件的話，右指針向右移動一位.

JAVA實作：

class Solution {
    public int minSubArrayLen(int target, int[] nums) {
        //原數組的長度
        int length = nums.length;
        //傳回的結果
        int ans = Integer.MAX_VALUE;
        //左指針
        int left = 0,right = 0;
        //視窗元素的和
        int sum = 0;
        //判斷邊界條件
        if(length == 0){
            return 0;
        }
        while(right < length){
            //右指針周遊數組
            sum += nums[right];
            while(sum >= target){
                //更新視窗
                sum -= nums[left];
                //尋找最小子數組
                ans = Math.min(ans,right-left+1);
                //左指針++
                left++;
            }
            //右指針++
            right++;
        }
        return ans == Integer.MAX_VALUE?0:ans;
    }
}
           

C++實作：

class Solution {
public:
    int minSubArrayLen(int s, vector<int>& nums) {
        int result = INT32_MAX;
        int sum = 0; // 滑動視窗數值之和
        int i = 0; // 滑動視窗起始位置
        int subLength = 0; // 滑動視窗的長度
        for (int j = 0; j < nums.size(); j++) {
            sum += nums[j];
            // 注意這裡使用while，每次更新 i（起始位置），并不斷比較子序列是否符合條件
            while (sum >= s) {
                subLength = (j - i + 1); // 取子序列的長度
                result = result < subLength ? result : subLength;
                sum -= nums[i++]; // 這裡展現出滑動視窗的精髓之處，不斷變更i（子序列的起始位置）
            }
        }
        // 如果result沒有被指派的話，就傳回0，說明沒有符合條件的子序列
        return result == INT32_MAX ? 0 : result;
    }
};