赞
踩
本题用到的算法:滑动窗口
题目要求找到一个子数组,也就是说不能对这个数组进行排序等操作。
滑动窗口:
在这个滑动窗口中,left和right是同向的指针,都会向右边移动。
我们规定一个sum,sum += nums[right] ,这样就能让sum作为滑动窗口里面的和,只需要让sum和target比较就行了。
因为sum只需要大于等于target就能够完成题目要求的,所以可能会出现多个left和right所在的位置里面的数字。此时再用一个len来记录滑动窗口里面的数字的个数,等到把所有的情况遍历完后,len值就是我们需要找到的那个数。
最终过程就分成了三步:
- class Solution {
- public int minSubArrayLen(int target, int[] nums) {
- int n = nums.length;
- int sum = 0;
- int len = Integer.MAX_VALUE;
- for(int left = 0, right = 0; right < n; right++){
- sum += nums[right];
- while(sum >= target){
- len = Math.min(len, right - left + 1);
- sum -= nums[left++];
- }
- }
- return len == Integer.MAX_VALUE ? 0 : len;
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。