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

相关文章

来自专栏Script Boy (CN-SIMO)

Codeforces Round #234A

Inna and choose option     题意: 一个由12个字符('O'或'X')组成的字符串,这12个字符可以排列成a*b(a*b=12)的...

2080
来自专栏猿人谷

二叉树的遍历——递归和非递归

二 叉树是一种非常重要的数据结构,很多其它数据结构都是基于二叉树的基础演变而来的。对于二叉树,有前序、中序以及后序三种遍历方法。因为树的定义本身就是 递归定义...

1878
来自专栏小樱的经验随笔

51Nod 1090 3个数和为0(暴力)

1090 3个数和为0 基准时间限制:1 秒 空间限制:131072 KB 分值: 5         难度:1级算法题 给出一个长度为N的无序数组,数组中的元...

2596
来自专栏Bingo的深度学习杂货店

Q26 Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in-place such that each element appe...

2475
来自专栏WindCoder

二叉树的动态链式存储实现—C语言

341
来自专栏编程理解

排序算法(五):堆排序

的时间复杂度即可将二叉树重新调整为有序状态。若构造出一种具有特殊节点顺序的二叉树,使得每次对二叉树执行插入或删除节点操作后,都调整保持二叉树根节点的值为树中节...

461
来自专栏和蔼的张星的图像处理专栏

算法1.排序二分查找及其变种

这个我也不知道能写多少,只是最近快放假了实在懒得看DSP了,而且卡在一个地方了,什么都不干又感觉心慌的很,所以又回头看看算法的东西。一些测试程序放在这里

742
来自专栏mukekeheart的iOS之旅

No.002 Add Two Numbers

Add Two Numbers Total Accepted: 160702 Total Submissions: 664770 Difficulty: Med...

2305
来自专栏尾尾部落

[算法总结] 二分查找

二分查找法作为一种常见的查找方法,将原本是线性时间提升到了对数时间范围,大大缩短了搜索时间,但它有一个前提,就是必须在有序数据中进行查找。

692
来自专栏mukekeheart的iOS之旅

判断两个单链表是否相交(有环、无环两种)

题目描述:   给定两个单链表的头节点head1和head2,如何判断两个链表是否相交?相交的话返回true,不想交的话返回false。   给定两个链表的头结...

2237

扫码关注云+社区