题目描述
给定一个含有 n 个正整数的数组和一个正整数 s ，找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组，返回 0。
示例:
输入: s = 7, nums = [2,3,1,2,4,3]
输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。
进阶:
如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。
分析
这一题有3种方法可以做出来，分别是：
- 暴力破解
- 二分查找
- 双指针
我是在探索栏目中，学习双指针的时候第一次遇到这个题目的，所以本文只分析了双指针方法的解题思路。以后有机会再加上其他的思路。
双指针法
双指针的核心思想就是要维护两个指针：一个快指针和一个慢指针，并确定两个指针的移动策略。有了这个思路，再想一下这个题目里面双指针的移动策略应该怎么确定。
首先可以将元素尽量多地累计起来，让它们的和超过s，再按数组的索引，从小到大去掉一些元素，使元素和逼近s，并保持元素和大于等于s。这个时候，通过一左一右两个指针（索引）就可以计算出最小连续数组的长度。
源码
public int minSubArrayLen(int s, int[] nums)
{
int len = nums.length;
int ans = Integer.MAX_VALUE;
int left = 0;
int sum = 0;
for (int i = 0; i < len; i++)
{
sum += nums[i]; // 把前i个元素累加起来
while (sum >= s)
{
ans = Math.min(ans, i - left + 1);
sum -= nums[left++]; // 依次剔除元素，使sum尽量接近s
}
}
return (ans != Integer.MAX_VALUE)? ans : 0;
}
测试用例
public static void main(String[] args)
{
MinimumSizeSubarraySum msss = new MinimumSizeSubarraySum();
int[] a = {2,3,1,2,4,3};
int s = 7;
int b = msss.minSubArrayLen(s,a);
System.out.println(b);
}
输出：2
