当前位置:   article > 正文

算法009:长度最小的子数组

算法009:长度最小的子数组

长度最小的子数组. - 备战技术面试?力扣提供海量技术面试资源,帮助你高效提升编程技能,轻松拿下世界 IT 名企 Dream Offer。icon-default.png?t=N7T8https://leetcode.cn/problems/minimum-size-subarray-sum/

本题用到的算法:滑动窗口

题目要求找到一个子数组,也就是说不能对这个数组进行排序等操作。

滑动窗口:

在这个滑动窗口中,left和right是同向的指针,都会向右边移动。

我们规定一个sum,sum += nums[right] ,这样就能让sum作为滑动窗口里面的和,只需要让sum和target比较就行了。

因为sum只需要大于等于target就能够完成题目要求的,所以可能会出现多个left和right所在的位置里面的数字。此时再用一个len来记录滑动窗口里面的数字的个数,等到把所有的情况遍历完后,len值就是我们需要找到的那个数。

最终过程就分成了三步:

  1. 初始化指针,建立滑动窗口,让right++
  2. 在right++的过程中,判定sum的值是否大于target
  3. 如果大于target,则记录当前len的值,此时的len值就是满足题目条件的其中一个值,不断重复上述过程,直到找到最小的那个len值;此时要注意,一旦找到了当前满足题意的组合,就需要让left向右移动,若不向右移动,sum的值只会比当前的大,len只会比当前的长
  1. class Solution {
  2. public int minSubArrayLen(int target, int[] nums) {
  3. int n = nums.length;
  4. int sum = 0;
  5. int len = Integer.MAX_VALUE;
  6. for(int left = 0, right = 0; right < n; right++){
  7. sum += nums[right];
  8. while(sum >= target){
  9. len = Math.min(len, right - left + 1);
  10. sum -= nums[left++];
  11. }
  12. }
  13. return len == Integer.MAX_VALUE ? 0 : len;
  14. }
  15. }

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/Li_阴宅/article/detail/750638
推荐阅读
相关标签
  

闽ICP备14008679号