滑动窗口应用场景:
最长连续子串等、最小和连续子集等问题,和动规的区别是动规可以划分出子集;
思维导图:
举例:
209. Minimum Size Subarray Sum
Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn't one, return 0 instead.
Example:
Input: s = 7, nums = [2,3,1,2,4,3]Output: 2Explanation: the subarray [4,3] has the minimal length under the problem constraint.
Follow up:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).
代码:
public class Solution {
public int minimumSize(int[] nums, int s) {
if(nums.length==0) return -1;
int i=0,j=0;int min = Integer.MAX_VALUE,sum=0;
for(i=0;i<nums.length;i++){
//sum = nums[i];
while(j<nums.length&&sum<s){
sum+=nums[j];
j++;
}
if(sum>=s)//排除j>=n跳出循环的情况
min = Math.min(min,j-i);
sum-=nums[i];
}
return min==Integer.MAX_VALUE? -1: min;//边界条件考虑,为空的时候,无解的时候
}
}