作者：whisper

链接：http://proprogrammar.com:443/article/203

声明：请尊重原作者的劳动，如需转载请注明出处

    一些题目用滑动窗口方法解题，可以将时间复杂度控制在 O(n) 级别，最重要的是定义好滑动窗口，明确它要表达的意思，当然边界和初始值非常重要。

    长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。

示例: 

输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

     说明：使用滑动窗口法，还使用了一个小技巧，在确定子数组长度时用了折半的方法以提高效率

public int minSubArrayLen(int s, int[] nums) {
        int max = slideWindowMax(nums, nums.length);
        if(max < s)
        {
        	return 0;
        }
        
        int low = 1;
        int high = nums.length;
        int mid = low;
        int result = low;
        
        while(low <= high)
        {
        	mid = (low + high) / 2;
        	max = slideWindowMax(nums, mid);
        	if(max < s)
        	{
        		low = mid + 1;
        	}
        	else if(max >= s)
        	{
        		high = mid - 1;
                result = mid;
        	}
        }
        
        return result;
    }
    
    public int slideWindowMax(int[] nums, int length)
    {
        int max = 0;
        int add;
        for(int i = 0; i < length; i++)
        {
        	max += nums[i];
        }
        add = max;
        
        for(int j = length; j < nums.length; j++)
        {
        	add = add - nums[j - length] + nums[j];
        	max = max(add, max);
        }
        
        return max;
    }
    
    public int max(int i, int j)
    {
    	return i >= j ? i : j;
    }

    我能想到的比较好的方法了，结果显示效率并不是太高，让我们看一下更高效的算法

public int minSubArrayLen(int s, int[] nums) {
        int p1=0;
        int p2=0;
        int sum = 0;
        int min = Integer.MAX_VALUE;
        while(p2<nums.length){
            sum+=nums[p2];
            p2++;
            while(sum>=s){
                if(p2-p1<min) min=p2-p1;
                sum-= nums[p1];
                p1++;
            }
        }
        if(min==Integer.MAX_VALUE) return 0;
        else return min;
    }

    这才是真正的滑动窗口啊，我上面的和这一比立马被比下去了，不过代码简洁了，就不是太好理解了，简单来说就是从前向后加的一个子数组如果满足条件，那么可能更短的子数组一定是去头的（去尾不行，因为是尾加满足的，去尾一定会不满足了）

    解题思路

    要求是连续子数组，所以我们必须定义 i，j两个指针，i 向前遍历，j 向后遍历，相当与一个滑块，这样所有的子数组都会在 [i...j] 中出现，如果 nums[i..j] 的和小于目标值 s，那么j向后移一位，再次比较，直到大于目标值 s 之后，i 向前移动一位，缩小数组的长度。遍历到i到数组的最末端，就算结束了，如果不存在符合条件的就返回 0。

    总结

    用了两种滑动法，显示自己写的不太好，而且还是参考别人的

    到这里数组类算法的学习也就完了，以后有时间会做其它的基础的题目并更新的。

    我们知道在准备面试的时候，刷算法题是一种捷径，特别是刷 LeetCode，但是不能一味的刷题，我们需要总结和思考，对于一些相似的题目我们应该多想想他们的思想，其实很多题的解题思路都是相近的。

亲爱的读者：有时间可以点赞评论一下