[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 条评论
登录 后参与评论

相关文章

来自专栏章鱼的慢慢技术路

Aizu_Insertion Sort

1348
来自专栏King_3的技术专栏

leetcode-788-Rotated Digits(使用vector替代if else的逐个判断)

2626
来自专栏北京马哥教育

Python练手题,敢来挑战吗?

这到题用到了字符串的所有字母大写和所有字母小写和字符串拼接,复制,用到的函数有 json 将列表中的内容按照指定字符连接成一个字符串,

760
来自专栏mathor

线性表(一)

652
来自专栏desperate633

LeetCode LintCode和大于S的最小子数组Minimum Size Subarray Sum题目分析

给定一个由 n 个整数组成的数组和一个正整数 s ,请找出该数组中满足其和 ≥ s 的最小长度子数组。如果无解,则返回 -1。

732
来自专栏King_3的技术专栏

leetcode-209-长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 s ,找出该数组中满足其和 ≥ s 的长度最小的连续子数组。如果不存在符合条件的连续子数组,返回 0。

1093
来自专栏计算机视觉与深度学习基础

Leetcode 209 Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minima...

18410
来自专栏来自地球男人的部落格

[LeetCode] 40. Combination Sum II

【原题】 Given a collection of candidate numbers (C) and a target number (T), fi...

1805
来自专栏青青天空树

小白详细讲解快速幂--杭电oj2035-A^B

输入数据包含多个测试实例,每个实例占一行,由两个正整数A和B组成(1<=A,B<=10000),如果A=0, B=0,则表示输入数据的结束,不做处理。

943
来自专栏有趣的Python

玩转算法面试:(三)LeetCode数组类问题

数组中的问题其实最常见。 排序:选择排序;插入排序;归并排序;快速排序 查找:二分查找法 数据结构:栈;队列;堆 …… 如何写出正确的程序 建立一个基...

4454

扫码关注云+社区