【滑动窗口】之 长度最小的子数组

2023-12-23 20:07:43
209. 长度最小的子数组

暴力循环法:
  public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            //只要有个元素 > 目标值 就返回最小长度1
            if (sum >= target) {
                return 1;
            }
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                if (sum >= target) {
                    min = Math.min(min, j - i + 1);
                    break;//终止本次内循环 相当于left指针右移
                }
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }
执行用时:150 ms, 在所有 Java 提交中击败了6.65%的用户
内存消耗:41.4 MB, 在所有 Java 提交中击败了24.27%的用户
滑动窗口:使用队列相加(实际上我们也可以把它称作是滑动窗口,这里的队列其实就相当于一个窗口)

①我们把数组中的元素不停的入队,直到总和大于等于 s 为止,接着记录下队列中元素的个数;

②然后再不停的出队,直到队列中元素的和小于 s 为止

③接着再把数组中的元素添加到队列中……重复上面的操作,直到数组中的元素全部使用完为止。
这里以 [2,3,1,2,4,3] 举例画个图来看下

上面画的是使用队列,但在代码中我们不直接使用队列,我们使用两个指针,刚开始都指向队头;

 public int minSubArrayLen(int target, int[] nums) {
        int min = Integer.MAX_VALUE;
        int left=0,right=0;//left相当于出队,right相当于入队
        int sum=0;
        //当右指针指向队尾就结束
        while (right<nums.length){
            sum+=nums[right++];
            while (sum>=target){
                min=Math.min(min,right-left);//这里为什么不加一因为到下一行right已经+=1了
                sum-=nums[left];//队首出队
                left++;
            }
        }
        return min == Integer.MAX_VALUE ? 0 : min;
    }

文章来源:https://blog.csdn.net/m0_48904153/article/details/135169080
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。