leetcode 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.
For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint
思路：尺取即可。。好久没写，竟然调了半天。。。
1/* ***********************************************
2Author :111qqz
3Created Time :2017年04月13日 星期四 20时48分00秒
4File Name :209.cpp
5************************************************ */
6class Solution {
public:
1 int ruler(vector<int>nums,int tar,int n)
2 {
3 int head = 0;
4 int tail = 0;
5 int sum = 0 ;
6 int res = 0x3f3f3f3f;
7 while (tail<n&&head<=tail)
8 {
9 sum = sum + nums[tail];
10 if (sum>=tar)
11 {
12 res = min(res,tail-head+1);
13 while (sum>=tar&&head<tail)
14 {
15 sum-=nums[head];
16 head++;
17 }
18 if (sum>=tar)
19 {
20 res = min(res,tail-head+1);
21 }
22 else
23 {
24 head--;
25 sum+=nums[head];
26 res = min(res,tail-head+1);
27 }
28 }
1 tail++;
2 }
3 return res==0x3f3f3f3f?0:res;
4 }
1 int minSubArrayLen(int s, vector<int>& nums) {
2 int n = nums.size();
3 int res = ruler(nums,s,n);
4 return res;
}
};