|
题目：
给定一个含有?n?个正整数的数组和一个正整数 target 。
找出该数组中满足其和 ≥ target 的长度最小的 连续子数组?[numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
注意：
1，是连续的子数组
2，其和 ≥ target 的长度最小的?
示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组?[4,3]?是该条件下的长度最小的子数组。
滑动窗口算法：
* 在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 r 指针，和一个用于「收缩」窗口的 l 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。
下面是我的解体思路：
输入：target = 7, nums = [2,3,1,2,4,3]
left下标：0，right下标：-1；
1，left下标不动，right下标移动：
right下标移动到3，expect=2+3+1+2 ,expect>target。
2，right下标不动，left下标移动：
减去left下标所在的值，expect=2+3+1+2-2 ，left右移下标为1 ,expect>target。
将left下标为1下的值减去，expect=3+1+2-3 ，left右移下标为2，expect<target。
3，left下标不动，right下标移动：?
right下标移动到4，expect=1+2+4，expect=target。
4，right下标不动，left下标移动：
将left下的值减去，expect=1+2+4-1,left下标移动到3，expect<target
5，left下标不动，right下标移动：
right下标移动到5，expect加上其值，expect=2+4+3，expect>target。
6，right下标不动，left下标移动：
将left下的值减去，expect=2+4+3-2,left下标移动到4，expect=target，这时遍历结束，最小的连续子数组就是，left下标为4，right下标为5。所以值为2
java代码：
public int MinSubArrayLen(int target, int[] nums) {
int length = nums.length;
if (length == 0) {
return 0;
}
//预期的和
int expect = 0;
//左指针,右指针
int left = 0, right = -1;
//左结果下标，右结果下标
int resultLeftIndex = 1, resultRightIndex = Integer.MAX_VALUE;
while (right + 1 < length) {
++right;
//左指针不动，右指针右移，窗口增大，右指针移动到的值都相加
expect = expect + nums[right];
if (nums[right] == target) {
return 1;
}
//当expect>=target时，右指针不动，左指针向右移，窗口减小，减去左指针所在的值，直到expect<target
while (expect >= target && left <= right) {
if (right - left + 1 < resultRightIndex - resultLeftIndex + 1) {
resultRightIndex = right;
resultLeftIndex = left;
}
if (expect < target) {
break;
}
//减去左指针所在的值
expect = expect - nums[left];
left++;
}
}
if (resultRightIndex - resultLeftIndex + 1 == Integer.MAX_VALUE) {
return 0;
}
return resultRightIndex - resultLeftIndex + 1;
}
|