[LeetCode] 209. Minimum Size Subarray Sum

【原题】 Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint.

【解释】 给定一个数组,要求求出这个数组的一个子数组大于等于给定s的最小长度,子数组要求连续。 【思路】 思路一、 由于要求连续,我们可以使用两个指针,left和right。主要两个步骤: 1. right右移。 若当前的sum小于s,说明目前的数字太少了,我们让right指针向右移以期让子数组有更多的数字使其和大于或等于s。 2. left右移。若找到了这样的子数组,接下来,我们逐渐缩小子数组的范围,即使得left右移,以期能够找到最小长度的子数组使得其和大于等于s,知道其和小于s则可停止移动left。 如此循环,直到right到达数组的边界。 这种方法是O(n)的时间复杂度。

public class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int left=0,right=0;
         int minLen=Integer.MAX_VALUE;
         int sum=0;
         while(right<nums.length){
             while(sum<s&&right<nums.length)//步骤1
                 sum+=nums[right++];
             while(sum>=s){//步骤2
                minLen=Math.min(minLen, right-left);
                sum-=nums[left++];
             }
         }
          return minLen==Integer.MAX_VALUE?0:minLen;//若数组中不存在这样的子数组则返回零
         //return minLen;
    }
}

思路二、 一般的题目要求更快的时间复杂度,然而这个题目要求在完成一个O(n)的算法之后,要求在找出一个O(nlogn)的算法,也是神奇。Anyway,没想出来。但了解一下不同的思路也算长长见识,参考这里

举个栗子来说说思路吧。 数组为[2,3,1,2,2,4,3], s=7 首先开辟一个比原数组多1的数组sums,保留[0,i-1]下标的和。这个例子中sums数组为:[0,2,5,6,8,12,15]。 然后用查找最小的>=s+sums[i]的index为right。 为什么要这样呢?这说明i到right的元素之和是>=s的啊,这不就是题目所要求的吗?如i==0的时候,最小的大于等于s的是8,index为4,这说明长度为4的子数组>=s,按照同样的思想找到最短的那一个长度就行了。由于sums是一个有序数组,所以复杂度中的logn就是二分查找的复杂度。

public class Solution {
    public int binarySearch(int[] sums,int s,int cur){
        int left=cur,right=sums.length-1;
        while(left<=right){
            int mid=(left+right)/2;
            if(sums[mid]>=s+sums[cur])
                right=mid-1;
            else left=mid+1;
        }
        return left;
    }
    public int minSubArrayLen(int s, int[] nums) {
        int ans=nums.length+1;
        int[] sums=new int[nums.length+1];
        sums[0]=0;
        for(int i=0;i<nums.length;i++)sums[i+1]=sums[i]+nums[i];
        for(int i=0;i<sums.length;i++){
            int right=binarySearch(sums,s,i);
            if(right==nums.length+1) break;
            ans=Math.min(ans, right-i);
        }
        return ans==nums.length+1?0:ans;
    }}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏鸿的学习笔记

python的迭代器和生成器

迭代是数据处理的基础,迭代可以理解为是一种惰性求值。在python里迭代器和生成器是一回事,使用的是yield关键字。

521
来自专栏CRPER折腾记

JS数组去重!!!一篇不怎么靠谱的"深度"水文

数组去重,这是一个老梗了...今天我又拿出来说了... 我们在考虑全面一点的情况下,数组去重的实现,比如针对NaN,undefined,{}; 这其中涉及的知识...

934
来自专栏重庆的技术分享区

JS-我待this如初见

1182
来自专栏老马说编程

(30) 剖析StringBuilder / 计算机程序的思维逻辑

上节介绍了String,提到如果字符串修改操作比较频繁,应该采用StringBuilder和StringBuffer类,这两个类的方法基本是完全一样的,它们的实...

1916
来自专栏老马说编程

(31) 剖析Arrays / 计算机程序的思维逻辑

数组是存储多个同类型元素的基本数据结构,数组中的元素在内存连续存放,可以通过数组下标直接定位任意元素,相比我们在后续章节介绍的其他容器,效率非常高。 数组操作是...

1968
来自专栏Java帮帮-微信公众号-技术文章全总结

第十七天 集合-Collection&amp;增强for&amp;迭代器【悟空教程】

出现意义:面向对象语言对事物的体现都是以对象的形式,所以为了方便对多个对象的操作,就对对象进行存储,集合就是存储对象最常用的一种方式。

992
来自专栏奔跑的蛙牛技术博客

Java中实现的简单算法 && 计算二分查找次数

如果采用其他方式对列表进行排序可以使用List接口的sort方法传入一个Comarable的一个对象

792
来自专栏Python爱好者

Java基础笔记02

992
来自专栏编程理解

Java 枚举类型 enum

枚举类型是 Java 5 中增加的一个小特性,在此之前,实现枚举的方式为定义编译期常量形式。而代码中使用编译期常量的方式在理解性和安全性方面存在不足,单纯的常量...

1172
来自专栏Java帮帮-微信公众号-技术文章全总结

第七天 自定义数据类型ArrayList集合【悟空教程】

1495

扫码关注云+社区