雙指針之滑動窗口

雙指針除了上一篇講到的對撞指針之外，還有一種叫滑動窗口，話不多說，直接上題。

一.長度最小的子數組

這道題怎麼做呢？當然是用滑動窗口，標題都說了。。

首先設置兩個指針l和r,設置最小長度result為最終結果，接著r開始向右滑動，每次滑動一次求和sum，與s比較。

當遍歷到第四個數2時 ，此時sum已經大於7，這時候記錄下來長度result=（r-l+1），接著我們要看後面有沒有符合條件並且長度更小的，l右移直到sum

此時sum=6比s小，r指針繼續右移,

此時sum=10>7,記錄下此時的長度length=r-l+1; 這樣result的取值就是Math.min(length,result(上一步取的))；以此內推下去，會得到滿足條件的長度最小的解。

這個就是滑動窗口的解法，l和r根據某種特定條件一直滑動直到取到最終解。

根據這個原理，代碼就很快寫好了：

public class HuaDongChuangKou {
 public int minSubArrayLen(int s, int[] nums) {
 int result=Integer.MAX_VALUE; //結果
 if(nums == null) return 0;
 int l = 0; //左指針
 int r = 0; //右指針
 int sum = 0; //和
 while(r < nums.length){
 sum += nums[r];
 while(l <= r && sum >= s){
 result = Math.min(result,r - l + 1);
 sum -= nums[l];
 l++;
 }
 r++;
 }
 if(result == Integer.MAX_VALUE) {
 return 0;
 }else {
 return result;
 }
 }
}

時間複雜度O(N),空間複雜度O(1)，LeeCode上運行結果：