题目

给定一个由 n 个整数组成的数组和一个正整数 s ，请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解，则返回 -1。

样例

给定数组 [2,3,1,2,4,3] 和 s = 7, 子数组 [4,3] 是该条件下的最小长度子数组。

挑战

如果你已经完成了O(n)时间复杂度的编程，请再试试 O(n log n)时间复杂度。

解题

 定义两个指针，slow，fast,以先后速度向右走

fast先找到第一个是的sum>s的值

根据fast和slow计算当前子数组的长度

sum-=nums[slow]，寻找最后一个不满足sum>=s 的slow，每次更新子数组长度的最短值。

说明：

子数组是原始数组中连续的一部分

public class Solution {    /**     * @param nums: an array of integers     * @param s: an integer     * @return: an integer representing the minimum size of subarray     */    public int minimumSize(int[] nums, int s) {        // write your code here        if(nums ==null || nums.length <=0)            return -1;        int slow = 0;        int fast = 0;        int n = nums.length;        int sum = 0;        int minsize = n+1;        while(fast
        
         s 的下标                sum+=nums[fast];                fast++;            }            minsize = Math.min(minsize, fast - slow + 1);                        while(sum>=s){ // 去除左边，也满足sum
        

 

class Solution:     # @param nums: a list of integers     # @param s: an integer     # @return: an integer representing the minimum size of subarray    def minimumSize(self, nums, s):        # write your code here        if s == None or len(nums) == 0:            return -1;        lens = len(nums)        slow = 0        fast = 0        sum = 0        res = lens+1        while fast < lens:            while fast < lens and sum < s:                sum += nums[fast]                fast +=1            while slow < fast and sum>= s:                res = min(res,fast - slow)                sum -= nums[slow]                slow +=1        if res ==lens+1:            return -1        else:            return res

总耗时: 444 ms