leetcode209-长度最小的子数组

原题

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

示例:

输入: s = 7, nums = [2,3,1,2,4,3] 输出: 2
解释: 子数组 [4,3] 是该条件下的长度最小的连续子数组。

进阶:

如果你已经完成了O(n) 时间复杂度的解法, 请尝试 O(n log n) 时间复杂度的解法。

解法

思想

使用两个指针i、j从下标为0处开始遍历。如果i-j内的总数小于s,将j向后移动,如果i-j内的总数大于s,将i向后移动,直到获取所有子数组的长度,并比较出最短长度。

代码

class Solution {
    public int minSubArrayLen(int s, int[] nums) {
        int i = 0;
        int j = -1;
        int size = nums.length;
        int sum = 0;
        int min = 0;
        while(i<size&&j<size){
            if(sum>=s){
                if(min==0) min = j-i+1;
                else min = j-i+1<min?j-i+1:min;
                sum -= nums[i++];
            }else{
                if(j==size-1) return min;
                sum += nums[++j];
            }
        }
        return min;
    }
}

原创文章,作者:彭晨涛,如若转载,请注明出处:https://www.codetool.top/article/leetcode209-%e9%95%bf%e5%ba%a6%e6%9c%80%e5%b0%8f%e7%9a%84%e5%ad%90%e6%95%b0%e7%bb%84/

(1)
彭晨涛彭晨涛管理者
上一篇 2019年11月18日
下一篇 2019年11月22日

相关推荐

  • leetcode38-外观数列

    原题 「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下: 1. 1 2. 11 3. 21 4. 1211 5. 111221 1 被读作…

    算法 2020年4月30日
    0290
  • leetcode1103-分糖果II

    原题 排排坐,分糖果。 我们买了一些糖果 candies,打算把它们分给排好队的 n = num_people 个小朋友。 给第一个小朋友 1 颗糖果,第二个小朋友 2 颗,依此类…

    算法 2020年3月5日
    0140
  • 剑指offer50-第一个只出现一次的字符

    原题(来源Leetcode) 在字符串 s 中找出第一个只出现一次的字符。如果没有,返回一个单空格。 s 只包含小写字母。 示例: s = "abaccdeff" 返回 "b" s…

    算法 2020年6月10日
    0180
  • leetcode456-132模式

    原题 给定一个整数序列:a1, a2, ..., an,一个132模式的子序列 ai, aj, ak 被定义为:当 i < j < k 时,ai < ak &lt…

    算法 2020年1月30日
    0150
  • leetcode999-车的可用捕获量

    原题 999. 车的可用捕获量 - 力扣(LeetCode) 解法 思想 这道题题目有点难理解,其实就是上下左右搜索,质量有点低了。 代码 class Solution { cha…

    算法 2020年3月26日
    070
  • leetcode191-位1的个数

    原题 编写一个函数,输入是一个无符号整数,返回其二进制表达式中数字位数为 ‘1’ 的个数(也被称为汉明重量)。 示例 1: 输入: 000000000000000000000000…

    算法 2020年4月15日
    0120
  • leetcode25-K个一组翻转链表

    原题 给你一个链表,每 k 个节点一组进行翻转,请你返回翻转后的链表。 k 是一个正整数,它的值小于或等于链表的长度。 如果节点总数不是 k 的整数倍,那么请将最后剩余的节点保持原…

    算法 2020年5月9日
    0540
  • leetcode611-有效三角形的个数

    原题 给定一个包含非负整数的数组,你的任务是统计其中可以组成三角形三条边的三元组个数。 示例1: 输入: [2,2,3,4] 输出: 3 解释: 有效的组合是: 2,3,4 (使用…

    2020年2月8日
    070
  • leetcode8-字符串转换整数 (atoi)

    原题 请你来实现一个 atoi 函数,使其能将字符串转换成整数。 首先,该函数会根据需要丢弃无用的开头空格字符,直到寻找到第一个非空格的字符为止。接下来的转化规则如下: 如果第一个…

    算法 2020年4月3日
    0270
  • leetcode41-缺失的第一个正数

    原题 给你一个未排序的整数数组,请你找出其中没有出现的最小的正整数。 示例 1: 输入: [1,2,0] 输出: 3 示例 2: 输入: [3,4,-1,1] 输出: 2 示例 3…

    算法 2020年5月11日
    0130

发表回复

登录后才能评论