首页 > 其他 > 详细

滑动窗口

时间:2019-05-02 22:16:47      阅读:154      评论:0      收藏:0      [点我收藏+]

209 长度最小的子数组

https://leetcode-cn.com/problems/minimum-size-subarray-sum/submissions/

  首先是滑动窗口的思路,我感觉这种寻找满足某个条件的连续的子集,如这里的数组,可能还会在字符串里用到。

  但这题卡了我很久的是边界条件,下面这段代码,当循环退出的时候,right的值是没有被加到sum里的,所以right指向的位置是在sum数组的后面一个,所以最后计算结果的时候不是right-left+1,而是right-left,原因就是right在sum后面。

 while (sum<s && right<nums.length){
                sum+=nums[right];
                right++;
            }

  其次是初始条件如何设置,我一开是设置的left=right=0,这么设置是可以的,但是我把sum设置为了nums[0],这样就有问题了,因为循环里面的时候sum+=nums[0],如果开头sum=nums[0]这样同一个nums[0]加了两次。

 

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        if(nums.length==0){
            return 0;
        }
        int left=0;
        int right = 0;
        int sum=0;
        int result = Integer.MAX_VALUE;
        while (left<=right && right<nums.length){

            while (sum<s && right<nums.length){
                sum+=nums[right];
                right++;
            }
            
            while (sum>=s && left<right&& left<nums.length){
                result = (result>(right-left))?right-left:result;
                sum-=nums[left];
                left++;
            }
        }

        return result==Integer.MAX_VALUE?0:result;
    }
}

 

滑动窗口

原文:https://www.cnblogs.com/AshOfTime/p/10803538.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!