209. 长度最小的子数组 滑动窗口+二分法

209.长度最小的子数组

难度：中等
2020/6/28每日一题打卡
一般看到什么 子数组 连续 和 就应该想到前缀和和滑动窗口
题目描述

解题思路

1、暴力法

我好傻噢，直到求前缀和，但是不知道后续怎么做了，所以用暴力法遍历找到区间和大于s的区间

/*
		  * 209. 长度最小的子数组
		  * 2020/6/28每日一题打卡
		  */
		 public static int minSubArrayLen(int s, int[] nums) {
			 int min = Integer.MAX_VALUE;
			 int[] sum = new int[nums.length+1];
			 for (int i = 0; i < nums.length; i++) {
				sum[i+1] = sum[i] + nums[i];
			}
			 if(nums.length == 0 || sum[nums.length] < s)
		            return 0;
			 for (int i = 0; i < sum.length; i++) {
				if(sum[i] >= s) { //找到一个大于s的值
					int j = 0;
					while(sum[i]-sum[j] >= s) {
						j++;
					}
					min = Math.min(min, i-j+1);
				}
			}
			 return min;
		    }

时间复杂度差不多O(n2)了

2、滑动窗口法

用双指针维护一个连续子区间队列，计算子区间的和，如果子区间和大于s，更新最小长度，然后出队左端点元素直到不满足大于s

public int minSubArrayLen(int s, int[] nums) {
			 int min = Integer.MAX_VALUE,sum = 0;
			 int i = 0; //i当前区间左边界
			for (int j = 0; j < nums.length; j++) {  //j区间右边界
				sum += nums[j];
				while(sum >= s) {  //当总和大于s的时候，排除左边界直到总和小于s
					min = Math.min(min, j-i+1);
					sum -= nums[i++];
				}
			}
			 return min==Integer.MAX_VALUE?0:min;
		    }

3、二分查找

进阶里要求实现O(nlogn)，由于前缀和是递增的，很容易想到用二分法

对于计算出的前缀和，每个位置sum[i] ，因为目标是要找到sum[j] - sum[i] >= s，所以可以进行变形，目标是找到sum[j] >= s + sum[i]，令target = s + sum[i]
然后用二分查找模板，首先排除掉肯定不是解的 sum[j] < s + sum[i]，移动左端点。这样最后左端点值就是想要的，但是也有可能没找到符合要求的，所以要进行判断看看是不是我们需要的点

//用二分法解决
		 public int minSubArrayLen(int s, int[] nums) {
			 int min = Integer.MAX_VALUE,n = nums.length;
			 int[] sum = new int[n+1];
			 //先求出前缀和
			for (int i = 0; i < nums.length; i++) {
				sum[i+1] = sum[i] + nums[i];
			}
			//针对每个开始的位置i，找到最小的能让sum[j]-sum[i] >= s的j
			for (int i = 0; i <= n; i++) {
				int target = s + sum[i];
				int left = i,right = n;
				while(left < right) {
					int mid = left + (right-left)/2;
					//System.out.println(left+" "+right+" "+mid);
					if(sum[mid] < target) {
						left = mid + 1;
					}else {
						right = mid;
					}
				}
				if(sum[left] >= target) {
					min = Math.min(min, left-i);
				}
				
			}
			 return min==Integer.MAX_VALUE?0:min;
		    }